169. 多数元素

题目链接：169. 多数元素

题目描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

核心思考：Boyer-Moore 投票算法

为了满足 $O(N)$ 的时间与 $O(1)$ 的空间要求，最核心的解法是摩尔投票法 (Boyer-Moore Voting Algorithm)。

由于多数元素出现的次数大于数组总长度的一半，如果在遍历过程中将不同的元素进行两两抵消，最终剩下的未被完全抵消的元素，就一定是该多数元素。

我们可以维护两个变量：

1. ans：记录当前的候选多数元素。
2. times：记录当前候选元素的计数值。

遍历数组：

• 当 times == 0 时，说明前面的元素已经被两两抵消完毕，当前的元素 x 成为新的候选元素 ans，并将计数值设为 1。
• 如果不为 0，则判断当前遍历的元素 x 是否等于候选元素 ans。相同时增加计数，不同时减少计数实现抵消。

遍历完成后，最后的 ans 即为所求。

解题思路 (Python)

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

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 为数组长度。只需线性遍历一遍数组即可完成投票与对消逻辑判断。
• 空间复杂度：$O(1)$，通过实时抵消，只使用了两个额外的变量。