C++를 사용하여 정렬된 배열에서 k보다 큰 요소 수 찾기

이 문제에서는 N개의 정렬된 정수 값과 정수 k로 구성된 배열 arr[]이 제공됩니다. 우리의 임무는 정렬된 배열에서 k보다 큰 요소의 수를 찾는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

arr[] = {1, 2, 5, 7, 8, 9} k = 4

출력

4

설명

Elements greater than k = 4 are
5, 7, 8, 9

솔루션 접근 방식

문제에 대한 간단한 해결책은 0에서 N까지 배열에 루프를 사용하는 것입니다. 그런 다음 k보다 큰 첫 번째 요소에서 중지합니다. 그런 다음 남은 값의 수를 계산합니다.

예시

솔루션 작동을 설명하는 프로그램

#include <iostream>
using namespace std;
int findGreaterCount(int arr[], int n, int k){
   for(int i = 0; i < n; i++){
      if(arr[i] > k)
         return (n - i);
   }
   return -1;
}
int main(){
   int arr[] = { 1, 3, 5, 7, 7, 8, 12, 21};
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 5;
   cout<<"The number of elements greater than k is "<<findGreaterCount(arr, n, k);
   return 0;
}

출력

The number of elements greater than k is 5

위의 코드는 잘 작동하지만 프로그램의 시간 복잡도는 O(N)입니다.

또 다른 보다 효율적인 접근 방식은 이진 검색을 사용하여 k보다 큰 요소를 찾는 것입니다. 그런 다음 더 큰 요소의 개수를 반환합니다.

예시

솔루션 작동을 설명하는 프로그램

#include <iostream>
using namespace std;
int findGreaterCount(int arr[], int n, int k){
   int s = 0;
   int e = n - 1;
   int firstGreterEle = n;
   while (s <= e) {
      int mid = s + (e - s) / 2;
      if (arr[mid] > k) {
         firstGreterEle = mid;
         e = mid - 1;
      }
      else
         s = mid + 1;
   }
   return (n - firstGreterEle);
}
int main(){
   int arr[] = { 1, 3, 5, 7, 7, 8, 12, 21};
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 5;
   cout<<"The number of elements greater than k is "<<findGreaterCount(arr, n, k);
   return 0;
}

출력

The number of elements greater than k is 5