【C++】配列内のK番目に小さいペア距離を求める方法

問題の概要

整数型の配列が与えられたとき、すべてのペアの中からk番目に小さい距離を求めることを考えます。ここで、ペア (A, B) の距離とは、A と B の差の絶対値（|A − B|）を指します。

例として、入力が [1, 3, 8] の場合を見てみましょう。考えられるすべてのペアとその距離は以下の通りです。

• [1, 3] → 距離 2
• [3, 8] → 距離 5
• [1, 8] → 距離 7

このとき k = 2 であれば、2番目に小さい距離は 5（8 − 3）となります。

解法のアプローチ

この問題は、カウント配列（度数分布）を使ったシンプルな手法で解くことができます。手順は以下の通りです。

1. 配列のサイズを n、配列内の最大値を x とします。
2. サイズ x + 1 のカウント配列 cnt を用意します。
3. すべてのペア (i, j)（i < j）について、cnt[|nums[j] − nums[i]|] を 1 ずつ増やしていきます。
4. 距離 0 から x まで順に走査し、累積カウントが k 以上になった時点の距離が答えとなります。

この方法では、各ペアの距離を直接数え上げるため、二重ループによる O(n²) の計算が必要になりますが、実装が非常に直感的で理解しやすいのが大きな特徴です。

C++での実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        int n = nums.size();
        int x = 0;
        for(int i = 0; i < n; i++)x = max(x, nums[i]);
        vector <int> cnt(x + 1);
        for(int i = 0 ; i < n; i++){
            for(int j = i + 1; j < n; j++){
                cnt[abs(nums[j] - nums[i])]++;
            }
        }
        for(int i = 0; i <= x; i++){
            if(cnt[i] >= k)return i;
            k -= cnt[i];
        }
        return x;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,3,8};
    cout << (ob.smallestDistancePair(v, 2));
}

入力

{1,3,8}

出力

5

コードのポイントと計算量

このアルゴリズムは、まず配列内の最大値を求めてカウント配列のサイズを決定し、次にすべてのペアの距離を記録、最後に小さい距離から順に数えていくことで、k番目に小さい距離を特定します。

• 時間計算量： O(n² + x) — ペアの列挙に O(n²)、カウント配列の走査に O(x)
• 空間計算量： O(x) — 最大値に依存するカウント配列が必要

なお、より大規模な入力に対しては、二分探索とスライディングウィンドウを組み合わせることで O(n log W + n log n) に高速化する手法も知られています。要素数が少なく値の範囲が限られている場合は、本記事のようなカウント配列方式が最もシンプルで効果的です。