絶対差の合計が最小になる配列要素の求め方

今回は非常に興味深いアルゴリズムの問題を取り上げます。N 個の要素を持つ配列「a」が与えられたとき、次の式で表される絶対差の合計を最小化するような要素 x を求め、そのときの最小値を計算します。

|a[0] − x| + |a[1] − x| + … + |a[n−1] − x|

具体例

たとえば、配列が {1, 3, 9, 6, 3} の場合を考えてみましょう。このとき最適な x は 3 です。実際に計算すると以下のようになります。

|1 − 3| + |3 − 3| + |9 − 3| + |6 − 3| + |3 − 3| = 2 + 0 + 6 + 3 + 0 = 11

解法のポイント：中央値を使う

この問題の鍵となるのは、x として配列の中央値（メディアン）を選ぶことです。直感的には、各要素との距離の合計を最も小さくできる点は、データの分布の中心にあたる中央値だからです。

なお、配列のサイズが偶数の場合は中央値が 2 つ存在しますが、どちらを選んでも最適解になります。これは、2 つの中央値の間にある任意の値も同じ最小合計をもたらすためです。

アルゴリズム

minSum(arr, n)

begin
   sort array arr
   sum := 0
   med := median of arr
   for each element e in arr, do
      sum := sum + |e − med|
   done
   return sum
end

手順を整理すると以下の通りです。

1. 配列 arr を昇順にソートする
2. 合計値 sum を 0 で初期化する
3. 中央値 med を取得する（ソート済み配列なら arr[n/2]）
4. 各要素 e について |e − med| を sum に加算する
5. sum を返す

C++ による実装例

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int minSum(int arr[], int n){
   sort(arr, arr + n);
   int sum = 0;
   int med = arr[n/2];
   for(int i = 0; i<n; i++){
      sum += abs(arr[i] - med);
   }
   return sum;
}
int main() {
   int arr[5] = {1, 3, 9, 6, 3};
   int n = 5;
   cout << "Sum : " << minSum(arr, n);
}

実行結果

Sum : 11

計算量について

このアルゴリズムの時間計算量は、ソート処理が支配的となるため O(n log n) です。ソート後の中央値取得は O(1)、合計計算は O(n) で完了します。より高速にしたい場合は、クイックセレクト（Quickselect）を使えば平均 O(n) で中央値を求めることも可能です。