C++のソートされていない配列でk個の最も近い数を検索します

要素が少ない配列Aがあるとします。配列はソートされていません。他に2つの値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個の要素との差の最大ヒープを1つ作成します

• 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