C++で配列内の任意の2要素間の最小差を求める方法

問題の概要

n個の要素を持つ配列Aが与えられたとき、その配列内の任意の2つの要素間の最小の差（絶対差）を求めることを考えます。

例えば、A = [30, 5, 20, 9] の場合、答えは 4 になります。これは要素 5 と 9 の差が最小となるためです。

解法のアプローチ

この問題は、以下の手順で効率的に解くことができます。

• 配列を昇順（非降順）にソートする
• 最小差を表す変数を無限大（INT_MAX）で初期化する
• ソート後の配列で隣接する要素同士をすべて比較し、最小の差を記録していく

ソートを行うことで、最小の差は必ず隣接する要素間に存在することが保証されます。そのため、すべての要素の組み合わせを比較する必要がなく、計算量を大幅に削減できます。

計算量

ソートに O(n log n)、隣接要素の比較に O(n) かかるため、全体の時間計算量は O(n log n) となります。全ペアを総当たりで比較する O(n²) の方法と比べて効率的です。

実装例（C++）

#include<iostream>
#include<algorithm>
using namespace std;

int getMinimumDifference(int a[], int n) {
    sort(a, a+n);  // 配列を昇順にソート
    int min_diff = INT_MAX;  // 最小差を無限大で初期化
    for (int i=0; i<n-1; i++)
        if (a[i+1] - a[i] < min_diff)
            min_diff = a[i+1] - a[i];  // 隣接要素の差がより小さければ更新
    return min_diff;
}

int main() {
    int arr[] = {30, 5, 20, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Minimum difference between two elements is: " << getMinimumDifference(arr, n);
}

実行結果

Minimum difference between two elements is: 4

まとめ

配列をソートして隣接要素同士を比較するだけで、任意の2要素間の最小差を O(n log n) で求められます。ソートにより最小差が必ず隣接要素間に現れるという性質を利用した、シンプルかつ効率的な手法です。