LeetCode 169. Majority Element

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        majority = nums[0]
        count = 0
        for elm in nums:
            if majority == elm:
                count += 1
            else:
                if count > 0:
                    count -= 1
                else:
                    majority = elm
                    count = 1
        return majority

Boyer–Moore多数決アルゴリズムを用いたものらしい。
このアルゴリズムがなぜうまくいくのかを説明しているサイトは見つけられなかったので、コーディング面接の時は他の解法を使うのが良さそう。

例えば。
出現した文字の回数を数えて辞書に入れる。
出現回数が最大の文字はmax(dic, key=dic.get)で取って来られるらしい。