Pythonで解く「3回の操作後の最大値と最小値の最小差」を求めるアルゴリズム

配列 nums が与えられ、1回の操作で配列内の任意の1つの要素を好きな値に変更できるものとします。このとき、最大3回の操作を行った後の nums の最大値と最小値の差として考えられる最小値を求めるのがこの問題です。

例えば、nums = [3,7,2,12,16] の場合、出力は 1 になります。ソートすると [2,3,7,12,16] となり、大きい方から3つの要素(7, 12, 16)を2〜3の間の値に変更すれば、配列は例えば [2,3,2,2,2] のようになります。このとき最大値は3、最小値は2なので、差は1です。

解法のアプローチ

この問題は次の手順で解くことができます。

• 配列のサイズが4以下の場合は 0 を返します(3回の操作で残りのすべての要素を同じ値に揃えられるため)
• 配列 nums をソートします
• ans を無限大(float("inf"))で初期化します
• i を 0〜3 の範囲で繰り返します:
  • mi := nums[i](残す区間の最小値候補)
  • ma := nums[配列の長さ − (3−i+1)](残す区間の最大値候補)
  • ans := min(ma − mi, ans)
• ans を返します

ポイントは、ソート済みの配列に対して「小さい側から i 個、大きい側から 3−i 個を変更対象にする」という4通りのパターンをすべて試すことです。変更した要素は任意の値にできるため、残った連続区間の最大値と最小値の差が答えの候補になり、その中で最小のものが最終的な答えとなります。

実装例

def solve(nums):
    if len(nums) <= 4:
        return 0
    nums.sort()
    ans = float("inf")
    for i in range(4):
        mi = nums[i]
        ma = nums[-(3-i+1)]
        ans = min(ma-mi, ans)
    return ans

nums = [3,7,2,12,16]
print(solve(nums))

入力

[3,7,2,12,16]

出力

1

計算量

ソートに O(n log n)、その後の4パターンの確認は定数時間なので、全体の計算量は O(n log n) となります。追加のメモリ使用量もソート分のみで非常に効率的です。