Boyer-Moore多数決アルゴリズム

Boyer-Moore多数決アルゴリズムについて

タグ boyter-moore majority vote 最頻値 多数決 投票アルゴリズム

概要

  • どの要素が最も頻出するかをO(n)で計算できるアルゴリズム
  • 最初に適当に候補を選択し、発見すると確信度を高めていき、確信度が0で候補を入れ替えるようなアプローチ
    • ベイズ統計的な雰囲気
  • 多数決で決定できるときにワークするアルゴリズム

具体例

nums = [2,2,1,1,1,2,2]

def solve(nums):
    confidence = 0
    cand = None
    for num in nums:
        if confidence == 0:
            cand = num
        if cand == num:
            confidence += 1
        else:
            confidence -= 1
    return cand

assert solve(nums) == 2

参考