JavaScriptで各要素より小さい数の個数を求める関数を実装する方法

今回は、数値の配列を唯一の引数として受け取るJavaScript関数を作成する方法を解説します。この関数は、元の配列の各要素について、「その要素より小さい値がいくつあるか」を計算し、その個数を対応する位置に格納した新しい配列を返すものです。

問題の概要

例えば、次のような入力配列が与えられたとします。

const arr = [3, 5, 4, 1, 2];

この場合、期待される出力は以下の通りです。

const output = [2, 4, 3, 0, 1];

出力の意味を確認してみましょう。最初の要素「3」より小さい数は「1」と「2」の2つなので、結果の先頭は「2」になります。同様に「5」より小さいのは4つ（3, 4, 1, 2）、「4」より小さいのは3つ（3, 1, 2）、「1」より小さいのは0個、「2」より小さいのは1つ（1）となります。

実装例：二重ループによるシンプルなアプローチ

最も直感的な方法は、各要素に対して配列全体を走査し、より小さい値の個数をカウントすることです。

const arr = [3, 5, 4, 1, 2];

const smallerNumbersThanCurrent = (arr = []) => {
    const res = [];
    for (let i = 0; i < arr.length; i++) {
        let count = 0;
        for (let j = 0; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
                count++;
            }
        }
        res.push(count);
    }
    return res;
};

console.log(smallerNumbersThanCurrent(arr));

実行結果

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

[2, 4, 3, 0, 1]

処理の流れを解説

このコードの動作は以下のステップで説明できます。

1. 外側のループで、元の配列の各要素を順番に取り出します。
2. 内側のループで、注目している要素と配列内のすべての要素を比較します。
3. 注目している要素の方が大きければ、カウンター（count）を1増やします。
4. 内側のループが終わった時点でのカウント値を、結果配列（res）に追加します。
5. すべての要素の処理が完了したら、結果配列を返します。

別のアプローチ：ソートを活用した効率的な方法

二重ループの計算量はO(n²)ですが、ソートを利用するとより簡潔に書くこともできます。配列を昇順にソートしたコピーを作成し、各要素のインデックス位置が「それより小さい要素の個数」に一致するという性質を利用します。

const smallerNumbersThanCurrent = (arr = []) => {
    const sorted = [...arr].sort((a, b) => a - b);
    return arr.map(num => sorted.indexOf(num));
};

console.log(smallerNumbersThanCurrent([3, 5, 4, 1, 2]));
// 結果: [2, 4, 3, 0, 1]

重複した値が存在する場合はindexOfが最初に出現した位置を返すため、この方法では重複も正しく扱われます。データサイズが大きい場合は、計算量を考慮して実装方法を選択するとよいでしょう。