Boyer–Moore majority vote algorithm(過半数判定アルゴリズム)

何をするアルゴリズムか

時間計算量O(n)と空間計算量O(1)で、配列やリスト内の「多数派」の要素を見つけるためのアルゴリズムです。ここで「多数派」とは、配列のサイズの半分を超える回数出現する要素を指します。例えば、[3,2,3]の3であるとか、[1,2,2,2,3]の2とか。

どうやって調べるのか

[3,3,4,2,4,4,2,4,4]を例にとって示します。

変数の初期化

このアルゴリズムではcandidate(解となる数の候補)とcountという2つの変数を用います。まずはこれを初期化します。

candidate = None
count = 0

配列の走査

ここでは配列の各要素に対して以下の操作を行います。

1. 各要素に対して、countが0ならば、その要素を新たなcandidateとし、countを1にする。
2. もし現在の要素がcandidateと同じならば、countを1増やす。
3. 現在の要素がcandidateと異なる場合、countを1減らす。

具体的に示すと以下のような感じ。

Element	Candidate	Count	Action
3	3	1	count 0 → 新しい candidateを3に設定
3	3	2	一致 → count 1増加
4	3	1	不一致 → count 1減少
2	3	0	不一致 → count 0 → 新しい candidateを2に
4	4	1	count 0 → 新しい candidate 4 に設定
4	4	2	一致 → count 1増加
2	4	1	不一致 → count 1減少
4	4	2	一致 → count 1増加
4	4	3	一致 → count 1増加

結果

上記より、過半数を占めるのは4であるとわかりました。
尚、本当に過半数かどうか調べるにはもう一度配列を操作して出現回数を数える必要があります。

pythonでの実装

def BMMV(nums: list[int])-> int:
    candidate = 0
    count = 0
    for num in nums:
        if count == 0:
            candidate = num
        if candidate == num:
            count += 1
        else:
            count -= 1

あとがき

過半数を占める数字がcount upする分を少数派は消しきれないので、多数派が生き残るという考えから作られているようです。なんとなく言わんとする所はわかるものの、特に腑に落ちる感じはしないですね。よく出来てるなと思います。

参考文献