พิจารณาว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบน้อย อาร์เรย์ไม่ได้รับการจัดเรียง เรามีค่าอื่นสองค่า X และ k งานของเราคือการหาจำนวน k ขององค์ประกอบที่ใกล้ที่สุดของ X จากอาร์เรย์ A หากองค์ประกอบ 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
