আমরা কয়েকটি উপাদান সহ একটি অ্যারে A আছে বিবেচনা করুন. অ্যারে সাজানো হয় না. আমাদের আরও দুটি মান X এবং k আছে। আমাদের কাজ হল অ্যারে থেকে 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<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
