【JavaScript】最大頻度と同じ度数を持つ最短の連続部分配列の長さを求める方法

問題概要

本記事では、数値の配列 arr を引数として受け取るJavaScript関数を作成します。

この関数が求めるのは、「配列全体における任意の要素の最大出現頻度(度数)と同じ頻度を持つ連続した部分配列」のうち、最も短いものの長さです。

入出力の例

たとえば、関数に次の配列を渡した場合を考えてみましょう。

入力

const arr = [55, 77, 77, 88, 55];

出力

const output = 2;

出力の解説

この入力配列では、要素 55 と 77 がそれぞれ2回出現しているため、最大出現頻度は 2 となります。

そして、最大頻度と同じ頻度を持つ部分配列の中で最も短いものの長さは 2 です。そのため、関数は 2 を返します。

アプローチのポイント

この問題を効率的に解くには、以下の手順で処理を行います。

1. 各要素について、出現回数(頻度)と最初・最後に出現したインデックスを記録する。
2. 配列を走査しながら最大頻度を更新し、その頻度に達した要素については「最後の出現位置 − 最初の出現位置 + 1」で部分配列の長さを計算する。
3. 同じ頻度を持つ要素が複数ある場合は、より短い長さを採用する。

この方法なら、配列を一度だけ走査するだけで答えを得られるため、時間計算量は O(n) と非常に効率的です。

コード例

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

const arr = [55, 77, 77, 88, 55];

const shortestLength = (arr) => {
  let freq = 0;
  let len = Infinity;

  arr.reduce((acc, num, index) => {
    if (acc[num] !== undefined) {
      // 既出の要素なら頻度を増やし、最後の出現位置を更新
      acc[num].freq += 1;
      acc[num].range[1] = index;
    } else {
      // 初登場の要素なら情報を初期化
      acc[num] = {
        freq: 0,
        range: [index, index],
      };
    }

    if (acc[num].freq > freq) {
      // 最大頻度が更新された場合
      freq = acc[num].freq;
      len = acc[num].range[1] - acc[num].range[0] + 1;
    } else if (acc[num].freq === freq) {
      // 同じ頻度なら、より短い長さを採用
      len = Math.min(
        len,
        acc[num].range[1] - acc[num].range[0] + 1,
      );
    }

    return acc;
  }, {});

  return len;
};

console.log(shortestLength(arr));

実行結果

2

コードの解説

このコードでは、reduce を使って配列を一度だけ走査しながら処理を進めます。

• アキュムレータ acc には、各数値をキーとして「頻度(freq)」と「出現範囲(range:最初と最後のインデックス)」を格納します。
• すでに存在する要素であれば頻度を1つ増やし、range の終了位置を現在のインデックスで上書きします。
• 頻度がこれまでの最大値を超えた場合は、最大頻度とその長さを更新します。
• 頻度が最大値と等しい場合は、Math.min で既存の長さと比較し、より短い方を採用します。

こうすることで、配列全体の最大頻度と一致する連続部分配列のうち、最も短い長さを正確に求めることができます。