मान लें हमारे पास कुछ तत्वों के साथ एक सरणी A है। सरणी अनसॉर्टेड है। हमारे पास दो अन्य मान X और k हैं। हमारा कार्य सरणी A से X की k निकटतम तत्वों की संख्या ज्ञात करना है। यदि तत्व X सरणी में मौजूद है, तो यह आउटपुट में नहीं दिखाया जाएगा। यदि A = [48, 50, 55, 30, 39, 35, 42, 45, 12, 16, 53, 22, 56] और X = 35, k = 4 है। आउटपुट 30, 39, 42, 45 होगा।
इसे हल करने के लिए, हम हीप डेटा संरचना का उपयोग करेंगे। चरण इस तरह दिखेंगे:
पहले k तत्वों के अंतर के साथ एक मैक्स-हीप बनाएं
k+1 वें तत्व से शुरू होने वाले प्रत्येक तत्व के लिए, इन चरणों को दोहराएं
वर्तमान तत्व और x के बीच अंतर ज्ञात करें
यदि अंतर हीप के रूट से अधिक है, तो वर्तमान तत्व को अनदेखा करें
अन्यथा रूट को हटाने के बाद वर्तमान तत्व को हीप में डालें
अंत में हीप में k निकटतम तत्व होंगे
उदाहरण
#include <iostream>
#include <queue>
using namespace std;
void findKClosestNumbers(int arr[], int n, int x, int k) {
priority_queue> priorityQ;
for (int i = 0; i < k; i++)
priorityQ.push({ abs(arr[i] - x), i });
for (int i = k; i < n; i++) {
int diff = abs(arr[i] - x);
if (diff > priorityQ.top().first)
continue;
priorityQ.pop();
priorityQ.push({ diff, i });
}
while (priorityQ.empty() == false) {
cout << arr[priorityQ.top().second] << " ";
priorityQ.pop();
}
}
int main() {
int arr[] = {48, 50, 55, 30, 39, 35, 42, 45, 12, 16, 53, 22, 56};
int x = 35, k = 5;
int n = sizeof(arr) / sizeof(arr[0]);
findKClosestNumbers(arr, n, x, k);
}
आउटपुट
45 42 30 39 35
