【JavaScript】入力配列の各要素について「右側にある小さい要素の個数」を数えた配列を作成する方法

問題

数値の配列を受け取り、それをもとに出力用の配列を構築する JavaScript の関数を作成することを考えます。

出力配列の各要素には、入力配列の対応する要素よりも右側に存在し、かつその要素より小さい数値の個数を格納します。最後に、この配列を返します。

例えば、[6, 2, 8, 5, 1, 3] という入力に対しては、以下のような出力が期待されます。

• 6 の右側にある小さい数 → 2, 5, 1, 3 の 4 個
• 2 の右側にある小さい数 → 1 の 1 個
• 8 の右側にある小さい数 → 5, 1, 3 の 3 個
• 5 の右側にある小さい数 → 1, 3 の 2 個
• 1 の右側にある小さい数 → 0 個
• 3 の右側にある小さい数 → 0 個

コード例

以下が実際のコードです。

const arr = [6, 2, 8, 5, 1, 3];
const buildSmallerArray = (arr = []) => {
    let count;
    let base;
    const res = [];
    for (let i = 0; i < arr.length; i++) {
        base = arr[i];
        count = 0;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < base) count++;
        };
        res.push(count);
    };
    return res;
};
console.log(buildSmallerArray(arr));

出力

[ 4, 1, 3, 2, 0, 0 ]

コードの解説

この実装では二重ループを使っています。

1. 外側のループで、基準となる要素（base）を先頭から順に取り出します。
2. 内側のループで、基準要素より右側にあるすべての要素と比較し、基準より小さい数が見つかるたびに count をインクリメントします。
3. 各要素のカウント結果を順番に res 配列へ追加し、最後に結果として返します。

なお、このアプローチの時間計算量は O(n²) です。配列のサイズが非常に大きい場合は、Binary Indexed Tree（BIT）やマージソートを応用した手法で O(n log n) まで高速化することも可能ですが、シンプルさと可読性を重視するなら上記の二重ループによる実装が分かりやすくおすすめです。