요소가 거의 없는 배열 A가 있다고 가정합니다. 배열이 정렬되지 않았습니다. 두 개의 다른 값 X와 k가 있습니다. 우리의 임무는 배열 A에서 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