Trong bài toán này, chúng ta được cung cấp một mảng arr [] bao gồm N giá trị nguyên được sắp xếp và một số nguyên k. Nhiệm vụ của chúng ta là Tìm số phần tử lớn hơn k trong một mảng đã sắp xếp.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {1, 2, 5, 7, 8, 9} k = 4 Đầu ra
4
Giải thích
Elements greater than k = 4 are 5, 7, 8, 9
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là sử dụng một vòng lặp trên mảng từ 0 đến N. Và sau đó dừng lại ở phần tử đầu tiên lớn hơn k. Sau đó, đếm số giá trị còn lại.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The number of elements greater than k is 5
Đoạn mã trên hoạt động tốt nhưng độ phức tạp về thời gian của chương trình là O (N).
Một cách tiếp cận khác hiệu quả hơn là sử dụng tìm kiếm nhị phân để tìm các phần tử lớn hơn k. Và sau đó trả về số lượng các phần tử lớn hơn.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The number of elements greater than k is 5