LeetCode 169 · 多数元素：Boyer-Moore 投票算法，最优雅的 O(1) 空间解法

这道题最有趣的地方不在于答案本身而在于那个 O(1) 空间的解法——Boyer-Moore 投票算法。第一次看到的时候我愣了好一会儿不需要哈希表、不需要排序、不需要分治就两个变量扫一遍就能找到出现超过一半的元素是的而且原理极其巧妙。题目长什么样给定一个大小为n的数组nums返回其中的多数元素。多数元素是指在数组中出现次数大于⌊n/2⌋的元素。输入nums [2,2,1,1,1,2,2]输出2说人话就是数组里一定有一个元素出现次数超过一半把它找出来。题目保证这个元素一定存在所以不需要处理没有多数元素的情况。超过一半这个条件非常强——它意味着多数元素的数量比所有其他元素加起来还多。正是这个性质让 Boyer-Moore 算法成为可能。第一反应哈希表计数最直接的想法——遍历一遍用哈希表统计每个元素出现的次数然后找最大的。fromcollectionsimportCounterclassSolutionHash:defmajorityElement(self,nums:List[int])-int:countsCounter(nums)returnmax(counts,keycounts.get)维度值说明时间O(n)遍历一遍 查找最大值空间O(n)最坏情况每个元素都不同时间已经是最优了但空间不行。题目进阶要求 O(1) 空间哈希表显然不满足。利用排序中位数一定是多数元素因为多数元素超过一半所以排序后位于中间位置的元素一定是多数元素——不管多数元素怎么分布它一定覆盖中点。classSolutionSort:defmajorityElement(self,nums:List[int])-int:nums.sort()returnnums[len(nums)//2]维度值说明时间O(n log n)排序的代价空间O(1)原地排序空间满足了但时间退步了。能不能两全其美最优解Boyer-Moore 投票算法这是这道题的精髓。思路可以用一句话概括不同阵营互相抵消最后剩下的一定是多数元素。怎么理解投票把数组想象成一场选举每个数字代表一个候选人遍历数组就像逐个人投票我们维护一个候选人和一个计数器遇到同阵营的相同的数字计数器 1遇到不同阵营的不同的数字计数器 -1计数器归零时换一个新的候选人classSolution:defmajorityElement(self,nums:List[int])-int:count0candidateNonefornuminnums:ifcount0:candidatenum count(1ifnumcandidateelse-1)returncandidate为什么这一定能找到多数元素关键推理多数元素的数量 n/2其他所有元素加起来 n/2。 即使最坏情况——所有非多数元素都和多数元素抵消 抵消掉的多数元素数量 非多数元素总数 n/2 剩余的多数元素数量 多数元素总数 - 抵消掉的数量 n/2 - n/2 0 所以多数元素永远不会被完全抵消最后剩下的一定是它。跑一遍示例 2nums [2, 2, 1, 1, 1, 2, 2] i0: num2, count0 → 候选人设为 2, count1 i1: num2, 22 → 同阵营! count2 i2: num1, 1≠2 → 不同阵营! count1 i3: num1, 1≠2 → 不同阵营! count0 ← 归零了 i4: num1, count0 → 候选人换为 1, count1 i5: num2, 2≠1 → 不同阵营! count0 ← 又归零了 i6: num2, count0 → 候选人换为 2, count1 最终候选人 2 ✓注意中间候选人从 2 变成了 1但最后又变回了 2。这就是抵消的过程——虽然中间状态看起来不对但最终结果一定是正确的因为多数元素的数量优势保证它不会被完全消灭。再跑一个更直观的例子nums [2, 2, 2, 2, 1, 1, 1] i0: num2, count0 → 候选人2, count1 i1: num2, 同阵营 → count2 i2: num2, 同阵营 → count3 i3: num2, 同阵营 → count4 i4: num1, 不同阵营 → count3 i5: num1, 不同阵营 → count2 i6: num1, 不同阵营 → count1 最终候选人 2 ✓ (2 出现 4 次1 出现 3 次)这个例子更清楚——多数元素从头到尾都是候选人其他元素只是不断消耗计数器但始终没能把 count 减到 0。三种解法放在一起看解法时间空间一句话评价哈希表计数O(n)O(n)最直观面试保底排序取中位数O(n log n)O(1)利用了排序后中点必是多数元素的性质Boyer-Moore 投票O(n)O(1)最优解两个变量扫一遍这道题教会我什么超过一半是一个极强的条件多数元素的数量比其他所有元素加起来还多。这个数量优势让它能在任何形式的对抗中存活。Boyer-Moore 本质上就是在模拟这种对抗——多数元素和不属于它的元素互相消耗多数元素永远不会被耗尽。这个思路可以推广如果某个东西的数量严格超过总量的一半那它一定能经受住任何成对抵消。最好的算法往往不需要额外数据结构哈希表是万能的但它不是免费的——O(n) 的空间不是小事。Boyer-Moore 告诉我们有时候问题本身的数学性质已经蕴含了答案不需要暴力地记录所有信息。只需要抓住最核心的不变量多数元素不会被完全抵消两个变量就足够了。代码短不代表思路简单Boyer-Moore 的代码只有 6 行但背后的数学推理一点都不简单。面试时如果被问到这道题光写出代码不够——你得能解释为什么 count 归零时可以放心换候选人。如果解释不清楚面试官会认为你是背的而不是理解的。完整测试代码fromtypingimportListclassSolution:defmajorityElement(self,nums:List[int])-int:count0candidateNonefornuminnums:ifcount0:candidatenum count(1ifnumcandidateelse-1)returncandidateclassSolutionSort:defmajorityElement(self,nums:List[int])-int:nums.sort()returnnums[len(nums)//2]classSolutionHash:defmajorityElement(self,nums:List[int])-int:fromcollectionsimportCounter countsCounter(nums)returnmax(counts,keycounts.get)if__name____main__:sSolution()nums[3,2,3]print(f输入:{nums}, 输出:{s.majorityElement(nums)})nums[2,2,1,1,1,2,2]print(f输入:{nums}, 输出:{s.majorityElement(nums)})nums[1]print(f输入:{nums}, 输出:{s.majorityElement(nums)})nums[6,5,5]print(f输入:{nums}, 输出:{s.majorityElement(nums)})nums[2,2,2,2,1,1,1]print(f输入:{nums}, 输出:{s.majorityElement(nums)})相关题目推荐LeetCode 229 · 求众数 II超过⌊n/3⌋的元素Boyer-Moore 的扩展版维护两个候选人LeetCode 1150 · 检查一个数是否在数组中占绝大多数有序数组中验证多数元素