JavaScriptで配列の多数派要素（過半数を占める要素）を見つける方法

サイズ n の配列が与えられたとき、その中に含まれる「多数派要素（majority element）」を見つける必要があります。多数派要素とは、配列の中で n / 2 回よりも多く出現する要素のことです。

多数派要素とは？

例えば配列の長さが 10 の場合、5 回より多く（つまり 6 回以上）出現する要素が多数派要素となります。性質上、このような要素は配列の中に最大で 1 つしか存在しません。

解決策：ハッシュマップで出現回数をカウントする

最もシンプルなアプローチは、各要素の出現回数をオブジェクト（ハッシュマップ）で記録しながら配列を走査し、出現回数が閾値（n / 2）を超えた時点でその要素を返す方法です。

const arr = [2, 4, 2, 2, 2, 4, 6, 2, 5, 2];

const majorityElement = (arr = []) => {
   // 過半数の基準となる閾値（n / 2 の切り捨て）
   const threshold = Math.floor(arr.length / 2);
   const map = {};
   for (let i = 0; i < arr.length; i++) {
      const value = arr[i];
      // 出現回数をカウント（初登場なら 1 からスタート）
      map[value] = map[value] + 1 || 1;
      // 閾値を超えた時点で多数派要素として返す
      if (map[value] > threshold)
         return value
   };
   // 多数派要素が存在しない場合
   return false;
};

console.log(majorityElement(arr));

出力結果

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

2

この配列では 2 が 6 回出現しており、10 / 2 = 5 を超えているため、多数派要素であることが確認できます。

コードのポイント解説

• 閾値の計算： Math.floor(arr.length / 2) で「n / 2 を超える」という条件の基準値を求めています。
• カウント処理： map[value] + 1 || 1 という書き方により、まだ登録されていない要素は自動的に 1 からカウントされます。
• 早期リターン： 多数派要素が見つかった時点ですぐに返すため、残りの要素を調べる無駄なループが発生しません。

計算量

このアプローチの時間計算量は O(n)、空間計算量は O(n) です。配列を一度だけ走査すればよいため、非常に効率的です。

多数派要素が存在しない場合

どの要素も n / 2 回を超えて出現しない場合、この関数は false を返します。用途に応じて null や -1、あるいは例外をスローするなど、戻り値の設計を変更してもよいでしょう。

補足：Boyer–Moore 投票アルゴリズム

空間計算量を O(1) に抑えたい場合は、ボイヤー・ムーア投票アルゴリズムが有効です。候補要素とカウンターを管理しながら配列を一度だけ走査するだけで多数派要素を特定でき、メモリ使用量を大幅に削減できます。