【LeetCode】169. 多数元素

1. 题目

2. 分析

说实话，这虽然是一道简单题，但我真没想到LeetCode官方题解会给出这么多种方案。下面就来谈谈如何在O(n)的时间复杂度下求出本题。

O(n)复杂度的解法挺难想到。本质上类似于消消乐游戏。如果一个元素是数组中的众数，那么很明显，将众数跟剩余的各个数相消，那么剩下来的那个数就是众数。那么问题来了，如何做到相消？仔细领悟下面这段代码。

3. 代码

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = nums[0]
        cnt = 0
        for num in nums:
            if cnt == 0: # 需要更换一个candidate
                candidate = num 
            if num == candidate:
                cnt += 1
            else:
                cnt -= 1
            # print(num, candidate, cnt)
        return candidate