在C ++中的未排序数组中查找k个最接近的数字

考虑我们有一个数组A，其中包含几个元素。数组未排序。我们还有另外两个值X和k。我们的任务是从数组A中找到k个最接近X的元素。如果元素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