【Python】配列の全要素を等しくするための最小移動回数を求めるアルゴリズム

問題の概要

空でない整数型の配列が与えられたとき、すべての要素を等しい値に揃えるために必要な「最小の移動回数」を求める問題を考えてみましょう。ここでいう1回の移動とは、選択した要素を +1（増加） または -1（減少） させる操作のことです。

たとえば、配列が [1, 2, 3] の場合を考えます。このとき出力は 2 になります。理由は以下の通りです。

• 1 を 1 回増加させて 2 にする
• 3 を 1 回減少させて 2 にする
• 2 はそのまま

合計 2 回の移動ですべての要素を 2 に揃えられるため、答えは 2 となります。

解決のためのアプローチ

この問題を効率的に解く鍵となるのが中央値（メディアン）です。手順は以下のようになります。

1. 配列 nums をソートする
2. カウンター（合計移動回数）を 0 で初期化する
3. 配列内の各要素 i について、中央値との差の絶対値をカウンターに加算する
   counter += abs(i - nums[len(nums) // 2])
4. カウンターの値を返す

なぜ「平均」ではなく「中央値」なのか

差の絶対値の合計を最小化する点において、最適な基準値は中央値であることが数学的に証明されています。外れ値（極端に大きい・小さい値）が存在する場合、平均値はその影響を強く受けてしまいますが、中央値は影響を受けにくいため、絶対誤差の総和を最小にできます。一方、二乗誤差の合計を最小化する場合は平均値が最適となる、という対比も覚えておくと理解が深まります。

Pythonでの実装例

以下のコードで実際の実装を確認してみましょう。

class Solution:
    def minMoves2(self, nums):
        nums.sort()
        counter = 0
        for i in nums:
            counter += abs(i - nums[len(nums) // 2])
        return counter

ob1 = Solution()
print(ob1.minMoves2([2, 5, 3, 4]))

入力

[2, 5, 3, 4]

出力

4

計算過程の解説

入力 [2, 5, 3, 4] をソートすると [2, 3, 4, 5] になります。要素数は 4 なので、中央値はインデックス 4 // 2 = 2 の位置にある 4 です。

各要素と中央値 4 との差の絶対値を合計すると、次のようになります。

• |2 − 4| = 2
• |3 − 4| = 1
• |4 − 4| = 0
• |5 − 4| = 1

合計は 2 + 1 + 0 + 1 = 4 となり、出力結果の 4 と一致します。

まとめ

このアルゴリズムは、ソートに O(n log n)、集計ループに O(n) の計算量で処理できる、シンプルかつ効率的な手法です。「絶対値の差の合計を最小化するなら中央値」というポイントを押さえておけば、同種の最適化問題にも応用できます。