【Python】不公平度が最小となる長さkの部分配列を見つけるアルゴリズム

問題の概要

配列 A と整数 k が与えられたとき、A から要素を取り出してサイズ k の配列 arr を作成し、「不公平度」と呼ばれる指標を最小化することを考えます。不公平度は次の式で計算されます。

( arr の最大値 ) − ( arr の最小値 )

たとえば、入力が A = [25, 120, 350, 150, 2500, 25, 35]、k = 3 の場合を考えてみましょう。このとき [25, 25, 35] を選べば、max(arr) = 35、min(arr) = 25 となり、その差は 10 になります。これより小さい差を実現できる組み合わせは存在しないため、答えは 10 です。

アルゴリズムの考え方

この問題は、ソート＋スライディングウィンドウというテクニックを使うことで効率的に解けます。

まず配列 A を昇順にソートします。すると、不公平度を最小にする k 個の要素の選び方は、必ず「ソート後の配列で連続した k 個」の中に含まれることが分かります。なぜなら、選んだ要素の間に別の要素を挟める状況があるなら、それを入れ替えることで最大値と最小値の差を縮める（少なくとも悪化させない）ことができるからです。

したがって、ソート後の配列上で大きさ k のウィンドウを左端から順にずらしながら「右端の値 − 左端の値」を比較し、その最小値を求めればよいことになります。

解く手順

• 配列 A を昇順にソートする
• n := A の要素数、m := A[n-1]（答えの候補を十分大きな値で初期化）
• i を 0 から n−k まで動かし、各 i について A[i+k−1] − A[i] を計算する
• A[i+k−1] − A[i] < m であれば、m をその値で更新する
• ループ終了後の m を答えとして返す

実装例

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

def solve(A, k):
    i = 0
    A.sort()              # 配列を昇順にソート
    n = len(A)
    m = A[n - 1]          # 答えの初期値（十分大きな値）
    x = 0
    y = 0
    while i <= n - k:                  # 大きさkのウィンドウを走査
        if A[i + k - 1] - A[i] < m:    # ウィンドウ内の最大値と最小値の差
            m = A[i + k - 1] - A[i]
        i += 1
    return m

A = [25, 120, 350, 150, 2500, 25, 35]
k = 3
print(solve(A, k))

入力

[25, 120, 350, 150, 2500, 25, 35]

出力

10

計算量

ソートに O(n log n)、ウィンドウの走査に O(n) が必要なため、全体の時間計算量は O(n log n) となります。可能な k 個の組み合わせをすべて総当たりで調べる方法（O(nCk)）と比べて非常に効率的で、要素数が多い配列でも現実的な時間で処理できます。