Pythonで中央値の絶対差が最小になるように数値リストを分割する方法

数値のリスト nums が与えられたとき、それを同じサイズの2つのグループに分割し、それぞれのグループの中央値の絶対差ができるだけ小さくなるようにすることを考えます。そして、その最小の差を求めるのがこの問題の目的です。なお、リストの長さを2で割った値（len(nums) / 2）は必ず奇数になると仮定します。

問題の例

たとえば、入力が [2, 10, 8, 5, 4, 7] の場合を考えてみましょう。このとき、[2, 5, 10] と [4, 7, 8] という2つのリストに分割できます。それぞれの中央値は 5 と 7 となるため、出力はその差である 2 になります。

解法のアプローチ

この問題は、一見複雑に思えますが、実は非常にシンプルな手順で解くことができます。鍵となるのは「リストをソートする」という操作です。ソート済みのリストを前半と後半に分けると、それぞれの中央値は必ずリスト全体の中央付近の隣接する2つの要素になります。n/2 が奇数であるため、前半の中央値はインデックス m-1 の要素、後半の中央値はインデックス m の要素に対応します。したがって、求めるべき最小の絶対差は次のように表せます。

• リスト nums を昇順にソートする
• m := len(nums) // 2（リストサイズを2で割った商）を計算する
• |nums[m] - nums[m-1]| を返す

計算量はソートに伴い O(n log n) となり、非常に効率的な解法です。

実装例

より理解を深めるために、以下のPythonコードを見てみましょう。

class Solution:
   def solve(self, nums):
      nums.sort()
      m = len(nums)//2
      return abs(nums[m] - nums[m-1])
ob = Solution()
print(ob.solve([2, 10, 8, 5, 4, 7]))

入力

[2, 10, 8, 5, 4, 7]

出力

2

まとめ

このアルゴリズムのポイントは、ソートによって中央値同士の関係が隣接要素の差に帰着することに気づくことです。ソート後のリストを半分に分ければ、両グループの中央値は必ず中央の隣接ペアになるため、追加の探索や組み合わせの検討は一切不要になります。わずか数行のコードで最適な分割を実現できる、エレガントな問題と言えるでしょう。