好的，我们这次来详细讲解 LeetCode 第 169 题「多数元素」。

1. 题目描述

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

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

• n == nums.length
• 1 <= n <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9

2. 题意理解

题目说“多数元素”出现次数 大于 n/2，这意味着：

1. 它出现的次数比其他所有元素加起来还要多。
2. 一定存在且只有一个这样的元素（题目已保证存在）。

所以我们要找的就是数组中的“众数”，并且它超过半数。

3. 思路演进

3.1 方法一：哈希表计数（最直观）

• 遍历数组，用哈希表记录每个数字出现的次数。
• 当某个数字的计数超过 n/2 时，直接返回它。
• 时间复杂度：O(n)
• 空间复杂度：O(n)（最坏情况需要存储 n/2 个不同数字）

伪代码：

count_map = {}
for num in nums:
    count_map[num] = count_map.get(num, 0) + 1
    if count_map[num] > n/2:
        return num

这个方法简单有效，但需要 O(n) 的额外空间。

3.2 方法二：排序法

• 将数组排序。
• 由于多数元素数量超过一半，那么排序后数组中间位置（下标 n//2）一定是多数元素。
• 时间复杂度：O(n log n)（由排序决定）
• 空间复杂度：O(1)（如果排序是原地排序）

示例：

nums = [2,2,1,1,1,2,2]
排序后：[1,1,1,2,2,2,2]
中间位置 index = 3 → nums[3] = 2

这个方法时间效率不如哈希表法，但代码简单。

3.3 方法三：Boyer-Moore 投票算法（最优解）

这是本题的经典 O(n) 时间、O(1) 空间的算法。

核心思想：

• 把多数元素记为 +1 票，其他元素记为 -1 票。
• 由于多数元素数量超过一半，最终“正”票数会胜出。

算法步骤：

1. 初始化候选元素 candidate 和计数器 count = 0。
2. 遍历数组：
   • 如果 count == 0，选择当前元素作为候选 candidate。
   • 如果当前元素等于 candidate，count++，否则 count--。
3. 遍历结束后，candidate 就是多数元素（题目保证存在，所以无需再验证；如果题目不保证存在，需要再遍历一次验证）。

为什么可行？

• 对抗思想：不同元素互相抵消，由于多数元素数量超过一半，所以最后剩下的必然是多数元素。

4. 逐步推演示例

以 nums = [2,2,1,1,1,2,2] 为例，n=7，多数元素需出现至少 4 次。

最终 candidate = 2，确实是多数元素。

5. 代码实现（Boyer-Moore 投票算法）

def majorityElement(nums):
    candidate = None
    count = 0
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    return candidate

6. 复杂度分析

• 时间复杂度：O(n)，一次遍历。
• 空间复杂度：O(1)，只用了两个变量。

7. 总结

• 本题展示了“空间最优”的投票算法，适用于找出现次数超过一半的元素。
• 如果题目不保证存在多数元素，需要第二次遍历验证 candidate 是否真的超过 n/2 次。
• 对比哈希表法，投票算法在空间上更优，适合大数据量场景。

这样讲解清楚了吗？我们可以继续下一个题目，或者你对这个题目的某部分还有疑问？