क्रमवारी लावलेल्या अ‍ॅरेमधील घटनांची संख्या मोजा


अडचण पातळी सोपे
वारंवार विचारले airbnb ऍमेझॉन सफरचंद ब्लूमबर्ग बाइट डान्स फेसबुक फ्लिपकार्ट Google संलग्न मेकमायट्रिप मायक्रोसॉफ्ट Netflix ओरॅकल क्विप ट्विटर उबेर यांडेक्स
अरे बायनरी शोध

समस्या विधान

“क्रमवारी लावलेल्या अ‍ॅरे मधील घटनांची संख्या” मध्ये आम्ही क्रमवारी दिली आहे रचना. X ची पूर्णांक संख्या असलेल्या क्रमवारीत असलेल्या अ‍ॅरेमध्ये घटनेची संख्या किंवा वारंवारतेची संख्या मोजा.

उदाहरण

इनपुट

13

1 2 2 2 2 3 3 3 4 4 4 5 5

3

उत्पादन

3

क्रमवारी लावलेल्या अ‍ॅरेमधील घटनांच्या संख्येसाठी 1 चा दृष्टिकोण

1. फक्त अशा प्रकारे सुधारित बायनरी शोध करा
2. याप्रमाणे एक्सची पहिली घटना शोधा:

  1.  अ‍ॅरेचा मधला घटक X बरोबर आहे का ते तपासा.
  2. जर समान किंवा जास्त घटक मध्यभागी असेल तर विभाजन सुरूवातीपासून मध्य -1 पर्यंत कमी करा. आपल्याकडे अ‍ॅरेच्या मध्यभागी डाव्या बाजूला पहिली घटना असेल.
  3. जर मध्यम घटक लहान असेल तर अ‍ॅरेची क्रमवारी लावल्यामुळे आम्ही मध्यम घटकाच्या उजव्या बाजूस तपासू.
  4. प्रथम घटना परत करा.

3. आता अशाप्रकारे अ‍ॅरेमधील एक्सची शेवटची घटना शोधा

  1. अ‍ॅरेचा मधला घटक X बरोबर आहे का ते तपासा
  2. जर समान किंवा लहान घटक मध्यभागी असेल तर विभाजन मध्य +1 वरून उच्च पर्यंत वाढवा. जसे की आपल्याकडे अ‍ॅरेच्या मध्यभागी उजव्या बाजूला शेवटची घटना असेल.
  3. अ‍ॅरेच्या डाव्या बाजूला अन्य शोध
  4. शेवटची घटना परत करा

4. आता घटनेची संख्या ही शेवटची घटना आहे - पहिली घटना +1.

अंमलबजावणी

सी ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;
int first_occurence(int arr[],int N,int X)
{
  int low = 0 , high = N-1;
  int first = INT_MAX;
  while(low <= high)
  {
    int mid = low + ((high-low)>>1);
    if(arr[mid] == X) //if found then check the left part for further occurence
    {
      if(mid < first)
      first = mid;
      high = mid-1;
    }
    else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
      low = mid + 1;
    else if (arr[mid] > X)//if middle element is larger than X check in left subpart
      high = mid - 1;
  }
  
  return first;
}
int last_occurence(int arr[],int N,int X)
{
  int low = 0 , high = N-1;
  int last = INT_MIN;
  
  while(low <= high)
  {
    int mid = low + ((high-low)>>1);
    if(arr[mid] == X) //if found check in right subpart for last occurence
    {
      if(mid > last)
      last = mid;
      low = mid+1;
    }
    else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
      low = mid + 1;
    else if (arr[mid] > X)//if middle element is larger than X check in left subpart
      high = mid - 1;
  }
  
  return last;
}
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
  int X; // number whose count is to be found out
  cin >> X;
  int count = 0; //initially its count is zero
  int last = last_occurence(a,n,X);
  if(last != INT_MIN)
    count += last;
  
  int first = first_occurence(a,n,X);
  if(first != INT_MAX)
    count -= first;
  cout<<last-first+1<<endl;  
  return 0;
}

जावा कार्यक्रम

import static java.lang.Math.min;
import java.util.Scanner;

class sum
{
    public static int first_occurence(int arr[],int N,int X)
    {
      int low = 0 , high = N-1;
      int first = 10000000;
      while(low <= high)
      {
        int mid = low + ((high-low)>>1);
        if(arr[mid] == X) //if found then check the left part for further occurence
        {
          if(mid < first)
          first = mid;
          high = mid-1;
        }
        else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
          low = mid + 1;
        else if (arr[mid] > X)//if middle element is larger than X check in left subpart
          high = mid - 1;
      }
      return first;
    }
    public static int last_occurence(int arr[],int N,int X)
    {
      int low = 0 , high = N-1;
      int last = -1;
      while(low <= high)
      {
        int mid = low + ((high-low)>>1);
        if(arr[mid] == X) //if found check in right subpart for last occurence
        {
          if(mid > last)
          last = mid;
          low = mid+1;
        }
        else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
          low = mid + 1;
        else if (arr[mid] > X)//if middle element is larger than X check in left subpart
          high = mid - 1;
      }
      return last;
    }
    public static int abs(int x)
    {
        if(x<0)
            x=x*-1;
        return x;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int X = sr.nextInt(); // number whose count is to be found out
        int count = 0; //initially its count is zero
        int last = last_occurence(arr,n,X);
        if(last != -1)
          count += last;
        int first = first_occurence(arr,n,X);
        if(first != 10000000)
          count -= first;
        System.out.println(last-first+1);
    }
}
8
1 1 2 2 2 3 4 5 
2
3

क्रमवारी लावलेल्या अ‍ॅरेमधील मोजणी संख्येसाठी गुंतागुंत विश्लेषण

वेळ कॉम्प्लेसिटी - ओ (लॉगएन) जेथे एन अ‍ॅरेचा आकार आहे. येथे आम्ही बायनरी शोध वापरतो ज्यामुळे आम्हाला लॉगएन वेळ गुंतागुंत होते.
स्पेस कॉम्प्लेक्सिटी - ओ (1) कारण आम्ही येथे कोणतीही सहाय्यक जागा वापरत नाही.

क्रमवारी लावलेल्या अ‍ॅरेमधील घटनांच्या संख्येसाठी 2 चा दृष्टिकोण

  1. फक्त अल्गोरिदम 1 सारखाच दृष्टिकोन करा परंतु अपर_बाउंड () आणि लोअरबाउंड फंक्शन्स वापरुन.
  2. अप्पर_बाउंड () आणि लोअर_बाउंड () फंक्शन्सद्वारे प्रथम घटकाचा वापर करून शेवटच्या घटकाची गणना करा.
  3. घटनांची संख्या फक्त अपर_बाउंड () द्वारा प्राप्त केलेली अनुक्रमणिका आहे -
  4. लोअर_बाउंड ().

लो_बाउंड (), अपर_बाउंड ही स्टँडर्ड टेम्पलेट लायब्ररी (एसटीएल) फंक्शन्स आहेत.

अंमलबजावणी

सी ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int X; // number whose count is to be found out
    cin >> X;
    int count = 0; //initially its count is zero
    count  = upper_bound(a,a+n,X) - lower_bound(a,a+n,X); 
    cout<<count;
    return 0;
}
8
1 1 2 2 2 3 4 5 
4
1

क्रमवारी लावलेल्या अ‍ॅरेमधील मोजणी संख्येसाठी गुंतागुंत विश्लेषण

वेळ कॉम्प्लेसिटी - ओ (लॉगएन) जेथे एन अ‍ॅरेचा आकार आहे. येथे आम्ही इनबिल्ट एसटीएल फंक्शन वापरतो ज्यामध्ये लॉगएन टाइम कॉम्प्लेक्सिटी असते.
स्पेस कॉम्प्लेक्सिटी - ओ (1) कारण आम्ही येथे कोणतीही सहाय्यक जागा वापरत नाही.

क्रमवारी लावलेल्या अ‍ॅरेमधील घटनांच्या संख्येसाठी 3 चा दृष्टिकोण

  1. फक्त एक पळवाट चालवा.
  2. जर आपल्याला X च्या बरोबरीचा एखादा घटक मिळाला तर संख्या वाढविणे सुरू करा
  3. जोपर्यंत आपण एक्स मोजणी वाढवत नाही हे समजत आहोत आणि तितक्या लवकर आपण एक्सपेक्षा वेगळी संख्या मिळवतो, नंतर प्राप्त केलेली संख्या ही क्रमवारी लावलेल्या अ‍ॅरेप्रमाणे प्रदर्शित करू.

स्पष्टीकरण

अ‍ॅरेच्या सुरुवातीपासून शेवटपर्यंत एक लूप चालवा आणि x == a [i] नंतर संख्या वाढवा हे तपासा. येथे एक उदाहरण घेऊ. a [] = {1, 2, 2, 2, 3, 4} आणि x = 2 नंतर x ची गणना 3 आहे. तर आपले अंतिम उत्तर 3 आहे.

अंमलबजावणी

सी ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int X; // number whose count is to be found out
    cin >> X;
    int count = 0; //initially its count is zero
    for(int i=0;i<n;i++)
    if(a[i]==X)
      count++;
    cout<<count;
    return 0;
}

जावा कार्यक्रम

import static java.lang.Math.min;
import java.util.Scanner;

class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int X = sr.nextInt(); // number whose count is to be found out
        int count = 0; //initially its count is zero
        for(int i=0;i<n;i++)
        if(arr[i]==X)
          count++;
        System.out.println(count);
    }
}
8
1 1 2 2 2 3 4 5 
1
2

क्रमवारी लावलेल्या अ‍ॅरेमधील मोजणी संख्येसाठी गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी - ओ (एन) कारण आपण संपूर्ण अ‍ॅरे ओलांडतो आणि x ची वारंवारता मोजतो.
स्पेस कॉम्प्लेक्सिटी - ओ (1) कारण आम्ही येथे कोणतीही सहाय्यक जागा वापरत नाही.

संदर्भ