JavaScriptでソート済み配列の過半数要素（マジョリティ要素）を判定する方法

過半数要素（Majority Element）とは？

長さ l の配列 arr における「過半数要素」とは、l / 2 回より多く出現する要素のことです。この性質上、そのような要素は最大でも 1 つしか存在しません。

ここでは、isMajority() という JavaScript 関数を作成します。この関数は第 1 引数として、常に昇順にソートされた配列 arr を受け取ります。

第 2 引数には検索対象となる数値を渡し、その数値が過半数要素であれば true を、そうでなければ false を返します。

たとえば、次のような配列と数値が与えられた場合を考えてみましょう。

const arr = [5, 5, 5, 12, 15];
const num = 5;

この場合の出力は次のようになります。

const output = true;

これは、5 が 3 回出現しており、配列の長さの半分である (5 / 2) = 2.5 よりも多く出現しているためです。

アルゴリズムのポイント：中央要素に注目する

この問題を解くうえで重要なのが、「配列がソート済みである」という前提条件です。もし過半数要素が存在するなら、それは必ず配列の中央の要素になります。なぜなら、その数値は少なくとも配列の半分以上にまたがって出現していなければならないからです。

この性質を利用すれば、中央の要素が目的の数値と一致するかどうかを確認するだけで、その数値が過半数要素かどうかを O(1) の時間計算量で判定できます。二分探索すら不要という点が、このアプローチの優れたところです。

実装例

実際のコードは以下のようになります。

const arr = [5, 5, 5, 12, 15];
const num = 5;
const isMajority = (arr = [], num = 1) => {
    const { length } = arr;
    if(!length){
        return false;
    };
    const middle = Math.floor(length / 2);
    if(arr[middle] === num){
        return true;
    }else{
        return false;
    };
};
console.log(isMajority(arr, num));

出力結果

コンソールに出力される結果は次のとおりです。

true