ボイヤー・ムーア多数決投票

初級

Boyer–Moore Majority Vote

ボイヤー・ムーア多数決投票は、配列の中で半分を超えて登場する過半要素を、1回の走査(O(n))と定数メモリ(O(1))だけで見つけるアルゴリズムです。1つの候補とその優勢度(count)だけを持ち歩きます。

基礎実装投票アルゴリズムO(n)

ボイヤー・ムーア多数決投票は、「過半（半分超）の要素が存在すればその値を見つける」アルゴリズムです。核心は候補(candidate)と優勢度(count)のたった2変数で、候補と異なる値が出るたびに票を1枚ずつ相殺することです。

1/18

配列の中で過半数（半分超）登場する「過半要素」を、1回の走査(O(n))と変数2個(O(1))だけで見つけます。候補(candidate)とその優勢度(count)だけを持って最後まで走査します。

初級

Boyer–Moore Majority Vote