力ボタン毎日1題(13)多数元素モル投票法

多数要素
**テーマ:**はnのサイズの配列を指定し、その多くの要素を見つけます.多くの要素は、配列に現れる回数がn/2⌋より大きい要素を指す.
配列は空ではなく、与えられた配列には常に多くの要素が存在すると仮定できます.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/majority-element著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
最初はpythonのdic辞書で直接書いた、すなわち配列をスキャンし、各要素の出現回数を統計しました.1つの要素がn/2を超える回数で現れると、その要素が返されます.
以下は知乎から見たモル投票法を引用して、方法の解釈はとてもイメージ的で、素晴らしいです!
構想:候補衆数candidateを初期化し、現在の候補衆数のcountを初期化する.先頭走査配列:候補衆数がそれと異なる要素に遭遇すると、両者は相殺され、候補衆数の数-1である.候補衆数が同じ要素に遭遇すると、候補衆数の数+1となる.
このとき,配列の末尾までスキャンすると,候補衆数が求められる衆数である.
ムーア投票法:
コアはスペル消費です.
諸侯が覇権を争うゲームをして、もしあなたの人口が総人口の半分以上を超えて、しかもすべての人口が戦争に出かけることができることを保証することができます.最後に生き残った国が勝利だ.
じゃ、大混戦ですね.最悪の人はみんな連合してあなたに対処します(カウンターとしての数を選ぶたびに衆数になります)、あるいは他の国も互いに攻撃します(カウンターの数として他の数を選択します)、しかし、あなたたちが内闘しない限り、最後にあなたが勝つに違いありません.
最後に残るのは必ず自分の人です.

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        candidate = 0
        count = 0
        for i in nums:
            if count == 0:
                candidate = i
            if i == candidate:
                count += 1
            else:
                count -= 1
        return candidate

出典:知乎(Zhihu)リンク:ムーア投票アルゴリズムをどのように理解しますか?-胡新辰の答えhttps://www.zhihu.com/question/49973163/answer/617122734