ציילן נומער פון פֿאַלן אין אַ סאָרטירט עריי  


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַירבנב אַמאַזאָן עפּל בלומבערג ביטעדאַנסע facebook פליפּקאַרט גוגל לינקעדין MakeMyTrip מייקראָסאָפֿט Netflix אָראַקל Quip טוויטטער ובער יאַנדעקס
מענגע ביינערי זוכן

פּראָבלעם סטאַטעמענט  

אין די "ציילן נומער פון פֿאַלן אין אַ סאָרטירט אַררייַ" פּראָבלעם, מיר האָבן געגעבן אַ סאָרטירט מענגע. ציילן די נומער פון פֿאַלן אָדער אָפטקייַט אין אַ סאָרטירט מענגע פון ​​X, וווּ X איז אַ גאַנץ נומער.

בייַשפּיל  

אַרייַנשרייַב

13

קסנומקס קסנומקס קסנומקס קסנומקס קסנומקס קסנומקס קסנומקס קסנומקס קסנומקס קסנומקס קסנומקס קסנומקס קסנומקס

3

רעזולטאַט

3

צוגאַנג 1 פֿאַר גראף נומער פון פֿאַלן אין אַ סאָרטירט אַררייַ  

1. סימפּלי טאָן אַ מאַדאַפייד ביינערי זוכן אַזאַ ווי
2. געפֿינען די ערשטע פּאַסירונג פון X ווי דאָס:

  1.  קוק אויב די מיטל עלעמענט פון די מענגע איז גלייַך צו X.
  2. אויב דער גלייך אָדער גרעסערער עלעמענט איז אין מיטן, רעדוצירן די צעטיילונג פון אָנהייב צו מיטן 1. ווי מיר וועלן האָבן די ערשטע פּאַסירונג אויף די לינקס זייַט פון מיטן מענגע.
  3. אויב די מיטל עלעמענט איז קלענערער, ​​מיר וועלן קאָנטראָלירן די רעכט זייַט פון די מיטל עלעמענט ווי די מענגע איז אויסגעשטעלט.
  4. ווייַזן די ערשטע פּאַסירונג.

3. איצט סימילאַרלי געפֿינען די לעצטע פּאַסירונג פון X אין די מענגע

  1. קוק אויב די מיטל עלעמענט פון די מענגע איז גלייַך צו X
  2. אויב דער גלייך אָדער קלענערער עלעמענט איז אין מיטן, פאַרגרעסערן די צעטיילונג פון מיטן 1 צו הויך. ווי מיר האָבן די לעצטע פּאַסירונג אויף די רעכט זייַט פון די מענגע.
  3. אַנדערש זוכן אין די לינקס זייַט פון די מענגע
  4. צוריקקומען די לעצטע פּאַסירונג
זע אויך
געפֿינען מינימום חילוק צווישן צוויי עלעמענטן

4. איצט די נומער פון פֿאַלן איז פשוט די לעצטע פּאַסירונג - ערשטער פּאַסירונג + 1.

ימפּלעמענטאַטיאָן

C ++ פּראָגראַם

#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;
}

Java פּראָגראַם

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

קאַמפּלעקסיטי אַנאַליסיס פֿאַר גראף נומער פון פֿאַלן אין אַ סאָרטירט עריי

צייט קאַמפּלעקסיטי - אָ (לאָגן) וווּ N איז די גרייס פון דעם מענגע. דאָ מיר נוצן אַ ביינערי זוכן וואָס פירט אונדז צו לאָגן צייט קאַמפּלעקסיטי.
ספעיס קאַמפּלעקסיטי - אָ (1) ווייַל מיר טאָן ניט נוצן קיין הילף פּלאַץ.

זע אויך
ציילן דיסטינקט עלעמענטן אין יעדער פֿענצטער פון גרייס ק

צוגאַנג 2 פֿאַר גראף נומער פון פֿאַלן אין אַ סאָרטירט אַררייַ  

  1. פשוט טאָן די זעלבע צוגאַנג ווי אַלגערידאַם 1, אָבער מיט Upper_bound () און Lower_bound פאַנגקשאַנז.
  2. רעכענען די לעצטע פּאַסירונג מיט upper_bound () און ערשטער פּאַסירונג via lower_bound () פאַנגקשאַנז.
  3. די נומער פון פֿאַלן איז סימפּלי דער אינדעקס באקומען דורך upper_bound () -
  4. לאָווער_באַונד ().

לאָוו_באָונד (), Upper_bound זענען פאַנגקשאַנז פֿאַר נאָרמאַל טעמפּלאַטע ביבליאָטעק (STL).

ימפּלעמענטאַטיאָן

C ++ פּראָגראַם

#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

קאַמפּלעקסיטי אַנאַליסיס פֿאַר גראף נומער פון פֿאַלן אין אַ סאָרטירט עריי

צייט קאַמפּלעקסיטי - אָ (לאָגן) וווּ N איז די גרייס פון דעם מענגע. דאָ מיר נוצן די STL פונקציאָנירן ינבוילד וואָס האט לאָגן צייט קאַמפּלעקסיטי.
ספעיס קאַמפּלעקסיטי - אָ (1) ווייַל מיר טאָן ניט נוצן קיין הילף פּלאַץ.

צוגאַנג 3 פֿאַר גראף נומער פון פֿאַלן אין אַ סאָרטירט אַררייַ  

  1. פשוט לויפן אַ שלייף.
  2. אויב מיר באַקומען אַן עלעמענט גלייַך צו רענטגענ, ינקריסינג די ציילן
  3. ביז מיר זען X פאַרגרעסערן די ציילן און ווי באַלד ווי מיר באַקומען אַ נומער אַנדערש פון X, מיר ווייַזן די באקומען ציילן ווייַל עס איז אַ סאָרטירט מענגע.

דערקלערונג

לויפן איין שלייף פון אָנהייב צו די סוף פון די מענגע און טשעק אויב x == a [i] און פאַרגרעסערן די קאַונץ. דאָ לאָזן אַ ביישפּיל. אַ [] = {1, 2, 2, 2, 3, 4} און x = 2, דער ציילן פון x איז 3. אַזוי, אונדזער לעצט ענטפער איז 3.

ימפּלעמענטאַטיאָן

C ++ פּראָגראַם

#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;
}

זע אויך
געפֿינען אַ סאָרטעד סאַבסאַקוואַנס פון גרייס 3 אין לינעאַר צייט

Java פּראָגראַם

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

קאַמפּלעקסיטי אַנאַליסיס פֿאַר גראף נומער פון פֿאַלן אין אַ סאָרטירט עריי

צייט קאַמפּלעקסיטי - אָ (ען) ווייַל מיר אַריבער די גאנצע מענגע און ציילן די אָפטקייַט פון רענטגענ.
ספעיס קאַמפּלעקסיטי - אָ (1) ווייַל מיר טאָן ניט נוצן קיין הילף פּלאַץ.

רעפֿערענצן