【JavaScript】配列内に過半数を占める要素があるかを判定してtrue/falseを返す方法

本記事では、重複した値を含む数値の配列を受け取り、配列の長さを n としたときに n/2 回よりも多く出現する要素（過半数要素）が存在するかどうかを判定する JavaScript 関数を作成します。該当する要素が存在すれば true を、存在しなければ false を返します。

アプローチ：ボイヤー・ムーア多数決アルゴリズム

この問題は「ボイヤー・ムーア多数決アルゴリズム（Boyer–Moore Voting Algorithm）」を用いることで、時間計算量 O(n)、追加メモリ O(1) という効率的な形で解くことができます。処理は大きく分けて次の2段階です。

1. 候補の決定：配列を先頭から順に走査し、現在の候補と同じ値が出たらカウントを +1、異なる値が出たら −1 とします。カウントが 0 になった時点で、その位置の値を新しい候補に切り替えます。
2. 候補の検証：最後に残った候補が、本当に配列全体の半分を超える回数出現しているかを実際に数えて確認します。過半数要素が存在しない場合でも何らかの候補は残るため、この検証ステップは省略できません。

コード例

const arr = [12, 5, 67, 12, 4, 12, 4, 12, 6, 12, 12];
const arr1 = [3, 565, 7, 23, 87, 23, 3, 65, 1, 3, 6, 7];

const findMajority = arr => {
   let maxChar = -Infinity, maxCount = 1;
   // ステップ1：過半数要素の候補を決定するループ
   for(let i = 0; i < arr.length; i++){
      if(maxChar !== arr[i]){
         if(maxCount === 1){
            maxChar = arr[i];
         } else {
            maxCount--;
         }
      } else {
         maxCount++;
      }
   }
   // ステップ2：候補が実際に過半数を占めているかを検証する
   const count = arr.reduce((acc, val) => maxChar === val ? ++acc : acc, 0);
   return count > arr.length / 2;
};

console.log(findMajority(arr));
console.log(findMajority(arr1));

実行結果

true
false

結果の解説

1つ目の配列は長さ 11 で、値 12 が 6 回出現しています。6 は 11 ÷ 2（5.5）より大きいため、true が返されます。

一方、2つ目の配列は長さ 12 ですが、どの値も半分を超える回数（7 回以上）出現していないため、false が返されます。

別解：オブジェクトで出現回数を数える方法

より直感的な実装として、各値の出現回数をオブジェクトで管理し、カウントが n/2 を超えた時点で即座に true を返す方法もあります。こちらは配列の後半部分の走査をスキップできるケースがあり、平均的には高速です。

const findMajoritySimple = arr => {
   const counts = {};
   for(const val of arr){
      counts[val] = (counts[val] || 0) + 1;
      if(counts[val] > arr.length / 2) return true;
   }
   return false;
};

console.log(findMajoritySimple([12, 5, 67, 12, 4, 12, 4, 12, 6, 12, 12])); // true
console.log(findMajoritySimple([3, 565, 7, 23, 87, 23, 3, 65, 1, 3, 6, 7])); // false

どちらの手法でも計算量は O(n) に収まるため、大きな配列でも問題なく動作します。メモリ使用量を最小限にしたい場合はボイヤー・ムーア法、可読性や早期リターンを重視する場合はカウント方式を選ぶとよいでしょう。