ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ที่ประกอบด้วยค่าจำนวนเต็ม N ค่าที่จัดเรียงแล้ว และจำนวนเต็ม k ภารกิจของเราคือ หาจำนวนองค์ประกอบที่มากกว่า k ในอาร์เรย์ที่จัดเรียงแล้ว
มาดูตัวอย่างเพื่อเข้าใจปัญหา
อินพุต
arr[] = {1, 2, 5, 7, 8, 9} k = 4
เอาต์พุต
4
คำอธิบาย
องค์ประกอบที่มากกว่า k = 4 คือ 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)
อีกวิธีที่มีประสิทธิภาพมากกว่าคือการใช้ binary search เพื่อหาองค์ประกอบที่มากกว่า 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
