用 C++ 在无序数组中找到 k 个最近的数字

假设我们有一个包含少数元素的数组 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

更新日期：2019-11-01

388 次浏览

开启您的 职业生涯

通过完成课程获得认证

立即开始
广告