C++で配列内の全要素ペアのk番目に小さい差を求めるプログラム

問題概要

いくつかの整数を含むリストが与えられます。配列内のすべての値のペアについて差を計算し、その中からk番目に小さい差を見つける必要があります。インデックスは0から始まり、値kは入力として与えられます。

例えば、入力が numbers = {2, 6, 4, 8}、k = 2 の場合、出力は 2 になります。

各ペア間の差は以下の通りです。

• (2, 6) = 4
• (2, 4) = 2
• (2, 8) = 6
• (6, 4) = 2
• (6, 8) = 2
• (4, 8) = 4

これらの値をソートすると「2, 2, 2, 4, 4, 6」となり、2番目に小さい値は 2 です（インデックスは0から開始）。

解法のアプローチ：二分探索

この問題は、差の候補値に対して二分探索を行うことで効率的に解けます。「mid以下の差を持つペアの個数」を数え、それがk以上であれば答えはmid以下、そうでなければmidより大きい、という性質を利用します。具体的な手順は以下の通りです。

• k を1増やす（0始まりのインデックスに対応させるため）
• 配列 input をソートする
• le := 0 とする
• ri := inputの最後の要素 − inputの最初の要素 とする
• le < ri の間、以下を繰り返す：
  • mid := (le + ri) / 2
  • tmp := 0、lp := 0 とする
  • i := 1 から input のサイズ未満まで、i を1ずつ増やしながら繰り返す：
    • input[i] − input[lp] > mid の間、lp を1ずつ増やす
    • tmp := tmp + i − lp
  • もし tmp >= k ならば、ri := mid とする
  • そうでなければ、le := mid + 1 とする
• le を返す

実装例

理解を深めるために、以下のC++実装を見てみましょう。

#include<bits/stdc++.h>

using namespace std;

int solve(vector<int>& input, int k) {
   k++;
   sort(input.begin(), input.end());
   int le = 0;
   int ri = input.back() - input[0];
   while (le < ri) {
      int mid = (le + ri) / 2;
      long long tmp = 0;
      int lp = 0;
      for (int i = 1; i < input.size(); i++) {
         while (input[i] - input[lp] > mid)
            lp++;
         tmp += i - lp;
      }
      if (tmp >= k)
         ri = mid;
      else
         le = mid + 1;
   }
   return le;
}
int main() {
   vector<int> numbers = {2, 6, 4, 8};
   cout<< solve(numbers, 2) <<endl;
   return 0;
}

入力

vector<int> numbers = {2, 6, 4, 8};
cout<< solve(numbers, 2) <<endl;

出力

2

計算量

ソートに O(n log n)、二分探索の各ステップではソート済み配列を走査してペア差の個数を数えるのに O(n) かかるため、全体の時間計算量は O(n log n + n log D) となります（D は最大差と最小差の範囲）。すべてのペアを列挙する O(n²) の素朴な手法と比べて、大幅に効率的である点がこのアプローチの大きな利点です。