Hãy xem xét chúng ta có một mảng A với ít phần tử. Mảng không được sắp xếp. Ta có hai giá trị khác X và k. Nhiệm vụ của chúng ta là tìm k số phần tử gần nhất của X từ mảng A. Nếu phần tử X có trong mảng thì nó sẽ không được hiển thị trong đầu ra. Nếu A =[48, 50, 55, 30, 39, 35, 42, 45, 12, 16, 53, 22, 56] và X =35, k =4. Đầu ra sẽ là 30, 39, 42, 45 .
Để giải quyết vấn đề này, chúng ta sẽ sử dụng cấu trúc dữ liệu heap. Các bước sẽ giống như bên dưới -
-
Tạo một đống chênh lệch tối đa với k phần tử đầu tiên
-
Đối với mọi phần tử bắt đầu từ phần tử thứ k +, hãy lặp lại các bước sau
-
Tìm sự khác biệt giữa phần tử hiện tại từ x
-
Nếu sự khác biệt lớn hơn gốc của heap thì bỏ qua phần tử hiện tại
-
Nếu không, hãy chèn phần tử hiện tại vào heap sau khi xóa phần tử gốc.
-
-
Cuối cùng đống sẽ có k phần tử gần nhất.
Ví dụ
#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);
} Đầu ra
45 42 30 39 35