JavaScriptでソートせずに配列の最大値と最小値の差を求める方法

ランダムな順序で並んだ数値の配列が与えられたとき、その配列を一切並べ替えることなく、含まれる最大値と最小値の差を返す関数を作成するのが今回の課題です。

配列をソートして最初と最後の要素を見る方法もありますが、ソートには O(n log n) の計算量が必要です。そこで本記事では、Array.prototype.reduce() を使って配列を一度だけ走査し、最大値と最小値を同時に追跡する効率的なアプローチを紹介します。この方法なら計算量は O(n) で済み、元の配列も変更されません。

実装例

まず、初期値として max: -Infinity と min: Infinity を持つオブジェクトをアキュムレータに設定します。そして各要素を走査しながら、現在の最大値・最小値より大きい・小さい場合はそれぞれ値を更新していきます。最終的に max - min を返すことで差が求まります。

const arr = [23, 65, 67, 23, 2, 6, 87, 23, 45, 65, 3, 234, 3];

const findDifference = arr => {
    // 空の配列の場合は 0 を返す
    if(!arr.length){
        return 0;
    }

    const creds = arr.reduce((acc, val) => {
        let { max, min } = acc;
        if(val > max){
            max = val;
        };
        if(val < min){
            min = val;
        };
        return { max, min };
    }, {
        max: -Infinity,
        min: Infinity
    });

    return creds.max - creds.min;
};

console.log(findDifference(arr));

出力結果

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

232

この配列の場合、最大値は 234、最小値は 2 なので、その差である 232 が出力されます。

補足：別の書き方との比較

スプレッド構文を使えば、Math.max(...arr) - Math.min(...arr) のように1行で書くことも可能です。ただし、この方法は要素数が非常に多い配列では引数の上限によりエラーになる可能性があります。一方、reduce() を使う本手法は配列のサイズに関係なく安全に動作するため、実務での利用におすすめです。