JavaScriptで各要素より小さい数の個数を数えて配列を作成する方法

JavaScriptで、数値の配列を引数として受け取る関数を作成する必要があります。

この関数は、入力された配列をもとに新しい配列を構築します。新しい配列の各要素には、元の配列において「その要素よりも小さい値を持つ要素の個数」が格納されます。

処理のイメージ

例えば、入力配列が次のようになっているとします。

const arr = [2, 7, 3, 1, 56, 4, 7, 8];

この場合、出力される配列は次のようになります。

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

それぞれの値がどのように求められているか見てみましょう。

• 最初の要素 2：自分より小さいのは 1 のみ → 1個
• 2番目の要素 7：自分より小さいのは 2, 3, 1, 4 の4つ（同じ値の7は含まない）→ 4個
• 5番目の要素 56：他のすべての要素より大きい → 7個

このように、重複する値は「自分自身」としては数えませんが、別の位置にある同じ値はカウント対象になります。

実装コード例

以下は二重ループを使ったシンプルな実装例です。

const arr = [2, 7, 3, 1, 56, 4, 7, 8];

const smallerThanCurrent = (arr = []) => {
    let { length } = arr;
    // 結果格納用の配列を0で初期化
    let res = Array(length).fill(0);
    
    // すべての要素同士を比較
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length; ++j) {
            // 自分自身以外かつ、自分より小さい値ならカウント
            if (i !== j && arr[i] > arr[j]) {
                ++res[i];
            }
        }
    }
    return res;
};

console.log(smallerThanCurrent(arr));

実行結果

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

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

コードのポイント

• Array(length).fill(0) を使うことで、入力配列と同じ長さの配列をすべて0で初期化できます。
• 外側のループ変数 i が基準となる要素、内側のループ変数 j が比較相手の要素です。
• i !== j という条件により、自分自身との比較を除外しています。これがないと、値が等しい場合でも誤ってカウントされてしまう可能性があります。

計算量について

この実装では全要素同士を比較するため、時間計算量は O(n²) となります。配列のサイズが小さければ問題ありませんが、大量のデータを扱う場合は、配列をソートしてからインデックスを利用する方法など、O(n log n) で処理できる手法を検討するとよいでしょう。