JavaScriptで絶対値の合計が最小になる整数xを求める方法

ソート済みの整数配列 arr が与えられたとします。このとき、次の式の値が最小となるような整数 x を見つけるのが課題です。

abs(a[0] - x) + abs(a[1] - x) + ... + abs(a[a.length - 1] - x)

ここで abs は絶対値を表します。条件を満たす答えが複数存在する場合は、その中で最も小さい値を出力します。

例

たとえば、

arr = [2, 4, 7]

の場合、出力は次のようになります。

absoluteValuesSumMinimization(arr) = 4

これは、abs(2 - 4) + abs(4 - 4) + abs(7 - 4) = 5 となり、他のどの数を選んでもこれ以上合計を小さくできないためです。

ポイント：中央値に注目する

絶対値の差の合計を最小化する x は、統計学の知識から「配列の中央値」であることが知られています。JavaScriptでは、配列の長さを使って中央値のインデックスを簡単に求められます。

arr.length / 2

この式は配列の長さの半分を返します。偶数長の配列では中央より右側の要素を、奇数長の配列ではちょうど中央の要素を指します。

• Math.ceil(arr.length / 2) は必要に応じて切り上げを行います。長さ5の配列なら 2.5 → 3 となるため、奇数長の配列ではインデックスが1つずれてしまいます。

• Math.ceil(arr.length / 2) - 1 とすればインデックスが1つ下がり、すべての配列でこのずれを修正できます。

コード例

以下は、各要素を候補として絶対値の合計を実際に計算し、最小となるものを返すコードです。

const arr = [2, 4, 7];
const absoluteValuesSumMinimization = (arr = []) => {
    const res = [];
    arr.forEach(num => {
        const sum = arr.reduce((accum, next) => {
            return accum + Math.abs(next - num);
        }, 0);
        res.push(sum);
    });
    const lowest = Math.min(...res);
    return arr[res.indexOf(lowest)];
};
console.log(absoluteValuesSumMinimization(arr));

出力

コンソールには次のように表示されます。

4

補足：より効率的なアプローチ

上記のコードは各候補ごとに合計を計算するため、計算量は O(n²) になります。しかし配列がすでにソート済みであれば、中央値（偶数長の場合は中央の2つのうち左側）を直接返すだけでよく、次のように O(1) で答えを求められます。

const absoluteValuesSumMinimization = arr => arr[Math.floor((arr.length - 1) / 2)];

大きな配列を扱う場合やパフォーマンスが重要な場面では、こちらの方法がおすすめです。