加拿大MLE面试算法题攻略：LeetCode 169 (Majority Element) Python解法 
大家好！最近在准备加拿大Machine Learning Engineer的面试，刷到一道经典题目——LeetCode 169 Majority Element，今天分享一下我的Python解法，希望能帮到也在备战面试的小伙伴们！
题目描述
给定一个大小为 n 的数组，找到其中的多数元素（出现次数超过 ⌊n/2⌋ 的元素）。假设数组非空，且多数元素一定存在。
示例：
Input:
Output: 3
解法1：哈希表统计法（Brute Force）
最直观的方法是统计每个元素的出现次数，然后返回出现次数最多的那个。
from collections import defaultdict
def majorityElement(nums):
counts = defaultdict(int)
for num in nums:
counts += 1
if counts > len(nums) // 2:
return num
时间复杂度： O(n)
空间复杂度： O(n)
解法2：排序法（Optimal for Short Code）
由于多数元素超过一半，排序后中间位置一定是它！
def majorityElement(nums):
nums.sort()
return nums
时间复杂度： O(n log n)（取决于排序算法）
空间复杂度： O(1)（如果原地排序）
解法3：Boyer-Moore投票算法（Optimal for O(1) Space）
这是最优解法，只需要O(1)空间，遍历一次数组即可！
def majorityElement(nums):
count = 0
candidate = None
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate
时间复杂度： O(n)
空间复杂度： O(1) 
总结
- 哈希表法：通用性强，适合统计类问题。
- 排序法：代码简洁，但时间稍差。
- Boyer-Moore算法：最优解，适合面试秀操作！
大家面试遇到过这道题吗？欢迎分享你的解法或优化思路！
祝大家Offer多多！
刚好在刷LC169，Boyer-Moore算法简直yyds！面试官上次还问“如果不用extra space怎么破”，直接掏出这个解法当场拿捏
比如
，适合白板coding手抖时保命（别问我怎么知道的…）
可能和本地优化有关？
