C++で3つのソート済み配列から最も近い3つの要素を効率的に検索する方法

3つのソート済み配列 A、B、C が与えられたとき、それぞれから要素 A[i]、B[j]、C[k] を選び、max(|A[i] − B[j]|、|B[j] − C[k]|、|C[k] − A[i]|) が最小になるような組み合わせを見つける問題を考えてみましょう。

例えば、A = [1, 4, 10]、B = [2, 15, 20]、C = [10, 12] の場合、答えは A から 10、B から 15、C から 10 の3つの要素となります。

配列 A、B、C のサイズをそれぞれ p、q、r とします。この問題は、配列がすでにソートされていることを利用して、3つのポインタを動かしながら線形時間で解くことができます。手順は以下の通りです。

• i := 0、j := 0、k := 0 で初期化する
• i < p かつ j < q かつ k < r の間、以下を繰り返す
  • A[i]、B[j]、C[k] の中から最小値と最大値を求める
  • diff := max(A[i], B[j], C[k]) − min(A[i], B[j], C[k]) を計算する
  • diff が現在の最小差より小さければ、結果を更新する
  • 最小値を含む配列のポインタを1つ進める

アルゴリズムのポイント

3つの値の最大差は「最大値 − 最小値」で決まります。配列は昇順にソートされているため、最大値を下げることはできません。そこで、最小値を含む配列のポインタを進めて最小値を大きくし、差が縮まる可能性を探るのがこのアルゴリズムの核心です。また、差が 0 になった時点でそれ以上改善できないため、ループを早期に終了できます。

実装例

#include <iostream>
using namespace std;

void getClosestElements(int A[], int B[], int C[], int p, int q, int r) {
    int diff = INT_MAX;
    int i_final = 0, j_final = 0, k_final = 0;
    int i = 0, j = 0, k = 0;
    while (i < p && j < q && k < r) {
        int min_element = min(A[i], min(B[j], C[k]));
        int max_element = max(A[i], max(B[j], C[k]));
        if (max_element - min_element < diff) {
            i_final = i, j_final = j, k_final = k;
            diff = max_element - min_element;
        }
        if (diff == 0)
            break;
        if (A[i] == min_element)
            i++;
        else if (B[j] == min_element)
            j++;
        else
            k++;
    }
    cout << A[i_final] << " " << B[j_final] << " " << C[k_final];
}

int main() {
    int A[] = {1, 4, 10};
    int B[] = {2, 15, 20};
    int C[] = {10, 12};
    int p = sizeof A / sizeof A[0];
    int q = sizeof B / sizeof B[0];
    int r = sizeof C / sizeof C[0];
    cout << "Closest elements are: ";
    getClosestElements(A, B, C, p, q, r);
}

実行結果

Closest elements are: 10 15 10

計算量

各ステップで必ずいずれかのポインタが1つ進むため、ループは最大で p + q + r 回しか実行されません。したがって、時間計算量は O(p + q + r)、追加で必要な空間計算量は O(1) となります。全組み合わせを総当たりで調べる O(p × q × r) の方法と比べて、非常に効率的なアプローチです。