この配列に多数派要素（マジョリティ要素）は含まれているか？ - JavaScript

問題の概要

数値の配列が与えられたとき、ある要素が配列の長さの半分（1/2）より多く出現していれば、その要素を「多数派要素（マジョリティ要素）」と呼びます。

例えば、配列の長さが7である場合を考えてみましょう。

このとき、配列内のいずれかの要素が少なくとも4回出現していれば、その要素は多数派要素とみなされます。また、1つの配列に存在しうる多数派要素は最大で1つだけであることも自明です。なぜなら、半分を超える出現回数を持つ要素が2つ以上存在することは論理的に不可能だからです。

私たちの課題は、重複した値を含む数値の配列を受け取り、多数派要素が存在する場合は true を、存在しない場合は false を返すJavaScript関数を実装することです。

サンプルコード

以下が実装例です −

const arr = [12, 5, 67, 12, 4, 12, 4, 12, 6, 12, 12];
const isMajority = arr => {
    let maxChar = -Infinity, maxCount = 1;
    // このループで多数派要素の候補を絞り込む
    for(let i = 0; i < arr.length; i++){
       if(maxChar !== arr[i]){
          if(maxCount === 1){
             maxChar = arr[i];
          }else{
             maxCount--;
          };
       }else{
          maxCount++;
       };
    };
    // このループで候補が実際に多数派要素であるかを検証する
    const count = arr.reduce((acc, val) => maxChar===val ? ++acc : acc, 0);
    return count > arr.length / 2;
};
console.log(isMajority(arr));

出力結果

コンソールには次の出力が表示されます −

true

アルゴリズムの解説

この実装は「ボイヤー・ムーア多数決アルゴリズム（Boyer–Moore Majority Vote Algorithm）」を応用したものです。処理の流れは以下の2段階に分けられます。

第1段階：候補の絞り込み

最初のforループでは、配列を走査しながら現在の候補要素と同じ値が出現すればカウントを増やし、異なる値が出現すればカウントを減らします。カウントが0になった時点で、新しい候補を採用し直すことで、最終的に多数派要素でありうる候補を1つに絞り込みます。

第2段階：候補の検証

第1段階で得られた候補は必ずしも多数派要素とは限らないため、reduce() を使って候補の出現回数を実際に数え、それが配列の長さの半分を超えているかどうかを確認します。

この手法の利点は、時間計算量が O(n)、追加メモリが O(1) で済む点です。Map やオブジェクトで出現回数を記録する方法と比べてメモリ効率が良く、大規模な配列でも高速に動作します。