面39-找出众数.md

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

摩尔投票法

• 票数和： 由于众数出现的次数超过数组长度的一半；若记 众数 的票数为+1 ，非众数 的票数为−1 ，则一定有所有数字的 票数和>0 。

• 票数正负抵消： 设数组 nums 中的众数为 xx ，数组长度为 nn 。若 nums 的前 aa 个数字的 票数和 = 0=0 ，则 数组后 (n-a)(n−a) 个数字 众数一定仍为 xx （即前 aa 个数字的票数正负抵消，后 (n-a)(n−a) 个数字的 票数和仍 > 0>0 ）。

  

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        votes = 0
        for num in nums:
            if votes == 0: x = num#当 票数 votesvotes 等于 00 ，则假设 当前数字 numnum 为 众数 xx ；
            votes += 1 if num == x else -1 #num = x时，票数 votes 自增 1；否则，票数 votes自减 1
        return x