JavaScriptで各要素より右側にある小さい数字の個数を数える方法

問題概要

今回は、数値の配列を唯一の引数として受け取るJavaScript関数を作成します。

この関数は、入力された配列をもとに新しい配列を生成します。新しく作られる配列の各要素には、元の配列内で「対応する要素より右側に位置し、かつその値より小さい要素」の個数が格納されます。

たとえば、次のような配列を入力したとします。

const arr = [4, 7, 1, 4, 7, 5, 3, 8, 9];

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

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

出力結果の解説

先頭の「4」よりも右側にあり、値がそれより小さい要素は「1」と「3」の2つです。続く「7」については、「1」「4」「5」「3」の4つが該当します。同様の手順ですべての要素について右側の小さい値を数えた結果が出力配列になります。

実装コード

実際のコードは以下の通りです。

const arr = [4, 7, 1, 4, 7, 5, 3, 8, 9];

// num より小さい要素の個数を数える
const countSmaller = (array = [], num) =>
  array.reduce((acc, val) => {
    if (val < num) {
      acc++;
    }
    return acc;
  }, 0);

// 各要素ごとに右側の小さい要素をカウント
const smallerArray = (arr = []) => {
  const res = [];
  for (let i = 0; i < arr.length; i++) {
    const el = arr[i];
    res[i] = countSmaller(arr.slice(i, arr.length), el);
  }
  return res;
};

console.log(smallerArray(arr));

出力

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

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

コードのポイント

countSmaller関数では、Array.prototype.reduce()を活用し、初期値0からスタートして条件に合致する要素だけをカウントしています。一方、smallerArray関数ではArray.prototype.slice()を使って現在のインデックス以降の部分配列を切り出すことで、各要素の「右側のみ」を対象としたカウントを実現しています。