算法刷题第12天｜LeetCode 169 多数元素：从暴力到最优解，一次吃透4种解法

算法刷题第12天｜LeetCode 169 多数元素：从暴力到最优解，一次吃透4种解法

大家好，这是我刷题打卡的第12天，今天搞定LeetCode 169 多数元素，顺便整理第二周学习小结～

📌 题目回顾

给定数组 nums，返回出现次数 > ⌊n/2⌋ 的元素，题目保证一定存在。
示例：

- [3,2,3] → 3
- [2,2,1,1,1,2,2] → 2

进阶要求：O(n) 时间 + O(1) 空间 。



🧩 四种解法全实现

1. 哈希表计数（最直观）

遍历数组，用哈希表统计次数，超过一半直接返回。

- 时间：O(n)
- 空间：O(n)

python
def majorityElement(nums):
from collections import defaultdict
cnt = defaultdict(int)
for num in nums:
cnt[num] += 1
if cnt[num] > len(nums)//2:
return num


优点：好写好懂；缺点：占用额外空间。

2. 排序取中位数（极简代码）

多数元素超过一半，排序后中间必为答案。

- 时间：O(n log n)
- 空间：O(log n)~O(1)

python
def majorityElement(nums):
nums.sort()
return nums[len(nums)//2]


一行搞定，面试快速写对很稳。

3. 分治法（递归思想）

把数组切成左右两半，分别求多数，再合并验证。

- 时间：O(n log n)
- 空间：O(log n)
适合练分治思路，工程里一般不用。

4. 摩尔投票法（最优解 ⭐）

核心：多数元素数量 > 其余总和，两两抵消最后必剩它。

- 时间：O(n)
- 空间：O(1)

python
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