JavaScriptで配列の次数と最短部分配列の長さを求める方法

配列の次数とは何か

配列の「次数（degree）」とは、その配列に含まれるいずれかの要素が出現する最大の頻度として定義される指標です。

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

たとえば上記の配列では、要素「3」が合計4回出現しています。そのため、この配列の次数は4となります。

課題の内容

今回求められているのは、リテラルの配列を引数として受け取るJavaScript関数の作成です。この関数の役割は、「配列全体と同じ次数を持つ連続した部分配列」のうち、最も長さが短いものの長さを求めることです。

実装例

以下のコードでは、Mapオブジェクトを活用してこの問題を効率的に解決しています。

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

const findShortestSubArray = (arr = []) => {
   // 各要素の [開始インデックス, 終了インデックス, 出現回数] を記録
   let range = new Map(), maxDegree = 0, minLength = Infinity;

   for(let i = 0; i < arr.length; i++){
      if(range.has(arr[i])) {
         let start = range.get(arr[i])[0];
         let degree = range.get(arr[i])[2];
         degree++;
         range.set(arr[i], [start, i, degree]);
         if(degree > maxDegree)
            maxDegree = degree;
      }
      else {
         let degree = 1;
         range.set(arr[i], [i, i, degree]);
         if(degree > maxDegree)
            maxDegree = degree;
      }
   }

   // 最大次数を持つ要素の中から最短の範囲を求める
   for (let key of range.keys()){
      let val = range.get(key);
      if(val[2] === maxDegree){
         let diff = (val[1] - val[0]) + 1;
         if(diff < minLength) minLength = diff;
      }
   }
   return minLength;
};

console.log(findShortestSubArray(arr));

コードの仕組み

このアルゴリズムのポイントは、Mapオブジェクトを使って各要素ごとに次の3つの情報を管理することです。

• 最初に出現したインデックス（開始位置）
• 最後に出現したインデックス（終了位置）
• 現在までの出現回数（次数）

1回目のループでは配列を走査しながら各要素の出現情報を更新し、同時に配列全体の最大次数を特定します。続く2回目のループでは、最大次数に一致する要素だけを取り上げ、「終了インデックス − 開始インデックス + 1」でその範囲の長さを計算し、最小値を求めます。

この手法により、時間計算量O(n)で問題を解くことができ、大きな配列でも高速に動作します。

実行結果

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

8

この結果「8」は、元の配列における要素「3」がインデックス2から9までの範囲に出現しているため、次数4を維持するには最低でもこの8要素分の部分配列が必要であることを意味します。