정렬 된 배열에서 발생 횟수 계산  


난이도 쉽게
자주 묻는 질문 Airbnb 아마존 Apple 블룸버그 게시물에서 ByteDance 페이스북 서비스 Flipkart 구글 링크드 인 MakeMyTrip Microsoft 넷플릭스 신탁 경구 트위터 동네 짱 Yandex 주차
배열 이진 검색

문제 정책  

"정렬 된 배열의 발생 수 계산"문제에서 정렬 된 정렬. X의 정렬 된 배열에서 발생 횟수 또는 빈도를 계산합니다. 여기서 X는 정수입니다.

예  

입력

13

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

3

산출

3

정렬 된 배열에서 발생 횟수에 대한 접근 방식 1  

1. 수정 된 이진 검색을 수행하여
2. 다음과 같이 X의 첫 번째 발생을 찾으십시오.

  1.  배열의 중간 요소가 X와 같은지 확인하십시오.
  2. 같거나 더 큰 요소가 중간에 있으면 파티션을 시작에서 중간 -1로 줄입니다. 배열 중간의 왼쪽에 첫 번째 발생이있을 것입니다.
  3. 중간 요소가 더 작 으면 배열이 정렬 될 때 중간 요소의 오른쪽을 확인합니다.
  4. 첫 번째 발생을 반환합니다.

3. 이제 유사하게 다음을 수행하여 배열에서 X의 마지막 발생을 찾습니다.

  1. 배열의 중간 요소가 X와 같은지 확인하십시오.
  2. 같거나 더 작은 요소가 중간에 있으면 파티션을 mid + 1에서 high로 늘립니다. 배열 중간의 오른쪽에 마지막 발생이있을 것입니다.
  3. 배열의 왼쪽에서 Else 검색
  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;
}

자바 프로그램

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

정렬 된 배열의 발생 횟수에 대한 복잡성 분석

시간 복잡성 – O (logN) 여기서 N은 배열의 크기입니다. 여기서 우리는 logN 시간 복잡성을 유도하는 이진 검색을 사용합니다.
공간 복잡성 – O (1) 여기에 보조 공간을 사용하지 않기 때문입니다.

참조
크기 K의 모든 창에서 고유 요소 계산

정렬 된 배열에서 발생 횟수에 대한 접근 방식 2  

  1. 알고리즘 1과 동일한 접근 방식을 수행하지만 upper_bound () 및 lower_bound 함수를 사용합니다.
  2. upper_bound ()를 사용하여 마지막 발생을 계산하고 lower_bound () 함수를 통해 첫 번째 발생을 계산합니다.
  3. 발생 횟수는 단순히 upper_bound ()로 얻은 인덱스입니다.
  4. 하한().

Low_bound (), 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

정렬 된 배열의 발생 횟수에 대한 복잡성 분석

시간 복잡성 – O (logN) 여기서 N은 배열의 크기입니다. 여기서 우리는 logN 시간 복잡도가있는 inbuild STL 함수를 사용합니다.
공간 복잡성 – O (1) 여기에 보조 공간을 사용하지 않기 때문입니다.

정렬 된 배열에서 발생 횟수에 대한 접근 방식 3  

  1. 간단히 루프를 실행하십시오.
  2. X와 같은 요소를 얻으면 개수를 늘리기 시작합니다.
  3. X가 카운트를 증가시키는 것을 볼 때까지 X와 다른 숫자를 얻는 즉시 얻은 카운트를 정렬 된 배열로 표시합니다.

설명

배열의 처음부터 끝까지 하나의 루프를 실행하고 x == a [i]인지 확인한 다음 개수를 늘립니다. 여기에 예를 들어 보겠습니다. a [] = {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의 정렬 된 하위 시퀀스 찾기

자바 프로그램

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

정렬 된 배열의 발생 횟수에 대한 복잡성 분석

시간 복잡성 – O (N) 전체 배열을 횡단하고 x의 주파수를 계산하기 때문입니다.
공간 복잡성 – O (1) 여기에 보조 공간을 사용하지 않기 때문입니다.

참조