ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ซึ่งประกอบด้วยค่าจำนวนเต็มที่เรียง N และจำนวนเต็ม k งานของเราคือ ค้นหาจำนวนองค์ประกอบที่มากกว่า 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
