Pythonで配列のマジョリティ要素（過半数を占める要素）を見つける方法

整数の配列が与えられたとき、その中で最も多く出現する要素（マジョリティ要素）を求めることを考えてみましょう。

問題の例

入力例1：

N = 8
A[ ] = { 1, 2, 4, 3, 3, 1, 1, 5 }

出力：

1

説明：この配列の中で最も多く出現している数は「1」です。したがって、出力は「1」となります。

入力例2：

N = 6
A[ ] = { 1, 5, 4, 4, 1, 1 }

出力：

1

説明：この配列でも最も多く出現しているのは「1」なので、「1」を結果として返します。

この問題へのアプローチ

配列に含まれる複数の整数の中から、最も頻度の高い要素を見つける必要があります。計算量O(n)・空間計算量O(n)の線形時間でこの問題を解くには、ハッシュマップ（辞書）を使うアプローチが効果的です。

このアプローチでは、「要素をキー、その出現回数を値」とするペアからなるハッシュマップを作成します。マップを走査しながら最大の出現回数を調べ、該当する数を結果として返します。

• サイズNの配列を入力として受け取ります。

• checkMajorityElement関数が、配列とそのサイズを引数に受け取り、最大頻度の数を返します。

• 配列の全要素について、「要素＝キー、出現回数＝値」となるハッシュマップを作成します。

• マップを反復処理し、出現回数がN/2を超える要素があれば、その数を結果として返します。該当する要素が存在しない場合は「-1」を返します。

補足：厳密な意味での「マジョリティ要素」とは、配列の長さの半分よりも多く出現する要素を指します。単なる最頻値（モード）とは異なるため、判定条件に「出現回数 > N/2」を使用している点に注意しましょう。

Pythonでの実装例

def check_majority_element(arr, N):
    mp = {}
    for i in range(N):
        if arr[i] in mp:
            mp[arr[i]] += 1
        else:
            mp[arr[i]] = 1
    for key in mp:
        if mp[key] > (N / 2):
            return key
    return -1

arr = [2, 1, 1, 2, 2, 2]
N = len(arr)
ans = check_majority_element(arr, N)
if ans != -1:
    print("マジョリティ要素は: %d" % ans)
else:
    print("配列にマジョリティ要素は存在しません")

実行結果

上記のコードを実行すると、次のような出力が得られます。

マジョリティ要素は: 2

この例では、配列 [2, 1, 1, 2, 2, 2] の中で「2」が6個中4回出現しています。これは全体の半分（3回）を超えているため、正しくマジョリティ要素と判定されます。

応用：collections.Counterを使った簡潔な書き方

Pythonでは標準ライブラリのcollections.Counterを利用すると、出現回数の集計をさらに簡潔に記述できます。

from collections import Counter

def check_majority_element(arr, N):
    counter = Counter(arr)
    for key, count in counter.items():
        if count > N / 2:
            return key
    return -1

どちらの実装でも計算量はO(n)であり、大きな配列に対しても効率的に動作します。