พิจารณาว่าเรามีอาร์เรย์ 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
เพื่อแก้ปัญหานี้ เราจะใช้โครงสร้างข้อมูล heap ขั้นตอนจะเป็นดังนี้ −
- สร้าง max-heap ของความต่างกับ k สมาชิกแรก
- สำหรับทุกสมาชิกตั้งแต่ k+1 เป็นต้นไป ทำซ้ำขั้นตอนเหล่านี้
- หาความต่างระหว่างสมาชิกปัจจุบันกับ x
- ถ้าความต่างมากกว่ารากของ heap ให้ข้ามสมาชิกปัจจุบัน
- มิฉะนั้น แทรกสมาชิกปัจจุบันลง heap หลังจากเอารากออก
- สุดท้าย heap จะมี 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
