Cho mảng A không sắp xếp, giá trị X và k. Tìm k phần tử gần X nhất. Nếu X có trong mảng thì không hiển thị. A=[48,50,55,30,39,35,42,45,12,16,53,22,56], X=35, k=4 → kết quả 30,39,42,45.
Dùng max-heap (priority_queue) lưu cặp (độ chênh lệch, chỉ số). Khởi tạo heap với k phần tử đầu. Với phần tử từ k+1 trở đi: tính độ chênh, nếu lớn hơn đỉnh heap thì bỏ qua, ngược lại pop đỉnh và push phần tử hiện tại. Cuối cùng heap chứa k phần tử gần nhất.
Ví dụ mã nguồn
#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()) {
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);
}
Kết quả đầu ra
45 42 30 39 35