सी ++ में एक क्रमबद्ध सरणी में के निकटतम संख्याएं खोजें

विचार करें कि हमारे पास कुछ तत्वों के साथ एक सरणी ए है। सरणी क्रमबद्ध नहीं है। हमारे पास दो अन्य मान X और k हैं। हमारा कार्य सरणी A से X के निकटतम तत्वों की k संख्या ज्ञात करना है। यदि तत्व X सरणी में मौजूद है, तो यह आउटपुट में नहीं दिखाया जाएगा। अगर ए =[48, 50, 55, 30, 39, 35, 42, 45, 12, 16, 53, 22, 56] और एक्स =35, के =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<pair<int, int> > 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