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

ソート済みの配列が与えられたとき、指定した数値 x がその配列の「過半数要素（majority element）」であるかどうかを判定する問題について解説します。

過半数要素（マジョリティ要素）とは

ある要素が過半数要素であるとは、その要素が配列内に n/2 回より多く出現することを指します。ここで n は配列のサイズです。

例えば、配列 {1, 2, 3, 3, 3, 3, 6}、x = 3 の場合を考えてみましょう。この配列には 3 が 4 回出現しており、配列のサイズは 7 なので、4 > 7/2 = 3 となり、3 は過半数要素であると言えます。したがって答えは true になります。

アプローチ

配列はソートされているため、同じ要素は必ず連続して並んでいます。この性質を利用すると、次のようなシンプルな手順で判定できます。

• 配列を先頭から走査し、x と等しい要素の出現回数を数えます。
• x より大きい要素が出現した時点でループを抜けます（ソート済みのため、それ以降に x は存在しない）。
• 出現回数が n/2 より大きければ true、そうでなければ false を返します。

この方法の計算量は O(n) です。

C++での実装例

#include <iostream>
using namespace std;

bool isMajorityElement(int arr[], int n, int x){
    int freq = 0;
    for(int i = 0; i < n; i++){
        if(arr[i] == x)
            freq++;
        if(arr[i] > x)
            break;
    }
    return (freq > n/2);
}

int main() {
    int arr[] = {1, 2, 3, 3, 3, 3, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x = 3;
    if (isMajorityElement(arr, n, x))
        cout << x << " は配列の過半数要素です";
    else
        cout << x << " は配列の過半数要素ではありません";
}

実行結果

3 は配列の過半数要素です

補足：二分探索による効率化

配列がソート済みであるという条件をさらに活かせば、二分探索を用いて x が最初に出現する位置（lower_bound）と最後に出現する位置（upper_bound）を求め、その差から出現回数を計算する方法もあります。この場合、計算量は O(log n) に抑えられます。

#include <iostream>
#include <algorithm>
using namespace std;

bool isMajorityElement(int arr[], int n, int x){
    int first = lower_bound(arr, arr + n, x) - arr;
    int last = upper_bound(arr, arr + n, x) - arr;
    return (last - first > n/2);
}

要素数が多い配列を扱う場合や、繰り返し判定を行う場合には、二分探索を利用したこちらの方法の方が効率的です。