C++で多数派要素（マジョリティ要素）を判定する方法

ソート済みの配列が与えられたとき、指定した数値 x がその配列の多数派要素（マジョリティ要素）であるかどうかを判定する問題を考えてみましょう。ある要素が配列の半分を超える回数（n/2 回より多く）出現するとき、その要素を多数派要素と呼びます。

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

アプローチ

最もシンプルな方法は、配列内に x が出現する回数を数え、その回数が n/2 より大きければ true を、そうでなければ false を返すというものです。配列がソートされているため、arr[i] が x より大きくなった時点でループを早期に終了することで、無駄な比較を省くことができます。

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; // ソート済みなので、xより大きい値が出たら終了
    }
    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 << " は配列の多数派要素ではありません";
}

入力

[1, 2, 3, 3, 3, 3, 6]
3

出力

3 は配列の多数派要素です

計算量と改善のポイント

上記の線形探索によるアプローチの時間計算量は O(n) です。ただし、配列がソート済みであることを活かせば、二分探索（lower_bound / upper_bound）を使って x の出現回数を O(log n) で求めることができ、全体の計算量を O(log n) まで改善できます。大規模な配列を扱う場合は、こちらの方法を検討するとよいでしょう。