C++でソートされていない配列からXに最も近い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 となります。

この問題を効率的に解くには、ヒープ(優先度付きキュー)データ構造を利用します。配列全体をソートするO(n log n)のアプローチと比べ、ヒープを使えばO(n log k)で処理でき、kが小さい場合に有利です。アルゴリズムの手順は以下の通りです。

• 最初のk個の要素について、Xとの絶対差をキーとして最大ヒープ(max-heap)を構築する
• k+1番目以降の各要素に対して、以下の処理を繰り返す
  • 現在の要素とXの差(絶対値)を計算する
  • その差がヒープのルート(現在の最大差)より大きい場合は、現在の要素を無視する
  • そうでない場合は、ヒープのルートを削除した上で、現在の要素をヒープに挿入する
• すべての要素を処理し終えると、ヒープにはXに最も近いk個の要素が残る

差が同じ値になる要素が複数存在する可能性があるため、実装では差とともに配列のインデックスもペアでヒープに格納しています。

C++実装例

#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

この実装では、k = 5 として実行したため、X = 35 に最も近い5つの要素 45, 42, 30, 39, 35 が出力されます。ヒープの操作は各要素につきO(log k)で済むため、大規模な配列でも効率的に動作する点がこの手法の大きな利点です。