मान लें हमारे पास कुछ तत्वों के साथ एक सरणी A है। हमारे पास दो अन्य मान X और k हैं। हमारा कार्य सरणी A से X के k निकटतम तत्वों की संख्या ज्ञात करना है। यदि तत्व X सरणी में मौजूद है, तो यह आउटपुट में नहीं दिखाया जाएगा। यदि A = [12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56] और X = 35, k = 4 है। आउटपुट 30, 39, 42, 45 होगा।
इसे हल करने के लिए, हम बाइनरी सर्च दृष्टिकोण का उपयोग करेंगे। इसका उपयोग करके हम क्रॉसओवर बिंदु प्राप्त करेंगे। यदि क्रॉसओवर बिंदु का सूचकांक मिल गया है, तो हम k-निकटतम तत्वों को O(k) समय में प्रिंट कर सकते हैं।
उदाहरण
#include <iostream>
using namespace std;
int getCrossoverPoint(int arr[], int left, int right, int x) {
if (arr[right] <= x)
return right;
if (arr[left] > x)
return left;
int mid = (left + right) / 2;
if (arr[mid] <= x && arr[mid + 1] > x)
return mid;
if (arr[mid] < x)
return getCrossoverPoint(arr, mid + 1, right, x);
return getCrossoverPoint(arr, left, mid - 1, x);
}
void findKClosestNumbers(int arr[], int x, int k, int n) {
int l = getCrossoverPoint(arr, 0, n - 1, x);
int r = l + 1;
int count = 0;
if (arr[l] == x) l--;
while (l >= 0 && r < n && count < k) {
if (x - arr[l] < arr[r] - x)
cout << arr[l--] << " ";
else
cout << arr[r++] << " ";
count++;
}
while (count < k && l >= 0) {
cout << arr[l--] << " ";
count++;
}
while (count < k && r < n) {
cout << arr[r++] << " ";
count++;
}
}
int main() {
int arr[] = {12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 35, k = 5;
findKClosestNumbers(arr, x, k, n);
}
आउटपुट
39 30 42 45 48
