最近在刷LeetCode热题100的Java题解遇到一个很有意思的现象很多标着“简单”的题反而是面试里最能拉开差距的题。“多数元素”Majority ElementLeetCode 169就是典型。题目本身一句话就能说清楚给定一个大小为 n 的数组找出其中出现次数大于 ⌊n/2⌋ 的元素题目保证这个元素存在。可就是这么一道题能延伸出暴力枚举、哈希表计数、排序取中位、分治、Boyer-Moore投票算法一整套解法链。很多人能把暴力解写出来也能用HashMap搞定但面试官追问一句“空间复杂度能不能降到O(1)”如果没提前研究过Boyer-Moore投票算法当场就容易卡住。这篇文章我准备用Java把从暴力到最优的整条链完整走一遍把每一步的复杂度、代码、坑和面试问法都摊开讲清楚适合正在准备Java后端面试、刷LeetCode热题100或者想系统梳理算法套路的朋友。1. 题目定位与思路总览1.1 多数元素问题到底在问什么先把这个题的条件抠清楚。输入是一个int数组nums长度记为n输出是一个int要求这个值在数组里出现的次数严格大于n/2。注意几个关键词严格大于也就是说如果n6那么多数元素至少出现4次才行出现3次只等于n/2不满足条件。题目还特别说明你可以假设数组非空并且给定的数组总是存在多数元素。这句话意味着很多东西比如在LeetCode 169这个主版本里你不需要额外写“不存在多数元素时返回什么”的逻辑。但面试官经常会在这个基础上做改动比如“如果不存在多数元素怎么办”这就是后话后面我会专门展开。这里有一个容易忽略的点多数元素如果存在有且只有一个。因为两个不同的数都超过n/2是不可能的这个基本盘想明白后面很多解法的正确性都好理解了。另外这道题在LeetCode上的“简单”标记其实有点迷惑性它代码量可以很小但背后的算法思维密度很高属于典型的“会写不等于懂懂也不等于讲得清”的题。1.2 五种解法路线图复杂度与适用场景在我实际刷题和学习的过程中这道题常见的解法有5种按复杂度排一下暴力枚举双层循环外层固定一个元素内层统计出现次数找到大于n/2就返回。时间复杂度O(n²)空间O(1)。哈希表计数一次遍历用HashMap记录每个元素出现次数统计过程中随时判断是否超过n/2超过就返回。时间复杂度O(n)空间O(n)。排序取中位先Arrays.sort然后直接返回下标为n/2的元素。时间复杂度O(n log n)空间O(1)取决于排序实现Java快排通常是原地。分治法把数组分成两半分别求左半和右半的多数元素如果两边返回相同值则直接返回否则分别统计两个候选值在全数组里谁出现更多。时间复杂度O(n log n)空间O(log n)。Boyer-Moore投票算法一次遍历维护一个候选人和一个计数器时间复杂度O(n)空间O(1)。我把这些信息整理成一张表面试时直接背出来就是加分点。解法时间复杂度空间复杂度代码量适用场景暴力枚举O(n²)O(1)很短数据量极小确认思路哈希表计数O(n)O(n)很短常规解法稳排序取中位O(n log n)O(1)最短不要求空间时随机化O(n)期望O(1)较短概率思维训练分治法O(n log n)O(log n)较长理解递归划分Boyer-MooreO(n)O(1)极短面试首选一个很关键的点是不同解法不只是复杂度的区别背后的算法思维是完全不同的。暴力是扫描直觉哈希表是计数思维排序是“中位数位置”洞察分治是递归划分Boyer-Moore是对消思想。面试官喜欢这道题就是因为它能一题考出候选人对基础数据结构和算法思维的掌握水平。所以这篇文章不只是给你一道题的答案而是给你一套完整的分析框架。2. 从暴力解法到哈希表新手最友好的两条路2.1 暴力枚举O(n²)的稳妥起步暴力解法最直白思路就是“我挑一个数看看它是不是俯视全场”。外层循环固定当前要验证的元素nums[i]内层循环从头到尾重新扫一遍统计nums[i]出现了多少次一旦发现count n/2就立刻返回nums[i]。代码长这样public int majorityElement(int[] nums) { int n nums.length; for (int i 0; i n; i) { int count 0; for (int j 0; j n; j) { if (nums[j] nums[i]) { count; } } if (count n / 2) { return nums[i]; } } return -1; }我为什么说它是“稳妥起步”因为它的正确性最容易验证几乎不会写错。但它的性能在n变大时非常感人每个元素都要扫一遍全数组实际执行次数接近n²。当n10万时理论上要执行100亿次比较这在任何笔试里都是超时警告。所以暴力解真正的作用不是交作业而是帮你快速确认题目条件以及作为后续优化方案的对照组。有一个小优化可以提一下外层循环如果已经检查过某个值其实没必要再次检查可以用一个set去重但这样空间开销就上去了本质上是在和哈希表方案做权衡。暴力解在面试里可以口头提一句“这种方案最直观但复杂度太高我一般不推荐作为最终实现”然后迅速过渡到哈希表反而显得你思路清晰。2.2 哈希表计数空间换时间的经典套路哈希表的思路非常贴近日常业务开发既然要统计出现次数那就用Map记录每个值的出现次数。一次遍历每个元素put到Map里计数值1然后立刻检查这个值是不是已经超过了n/2如果是就直接返回。这里用到Java的Map接口具体实现用HashMap。代码public int majorityElement(int[] nums) { int n nums.length; MapInteger, Integer counts new HashMap(); for (int num : nums) { counts.put(num, counts.getOrDefault(num, 0) 1); if (counts.get(num) n / 2) { return num; } } return -1; }getOrDefault是Java 8之后的标配作用就是从Map里取value取不到就返回默认值0然后1再放回去整个写法比先判断containsKey再get再put清爽很多。这个解法的优势是思路直观、编码快笔试时最不容易出错。但要注意空间开销最坏情况下n个元素全不相同Map里要存n个键值对空间复杂度O(n)。面试时如果你写的答案是这种面试官大概率会追问能不能把空间降到O(1)这就是5分和8分之间的差距。另外我要提一个很容易被忽略的细节这里判断条件是 counts.get(num) n / 2不是 。因为多数元素定义是“出现次数大于 n/2”如果n是偶数等于n/2并不满足条件。虽然题目保证一定存在多数元素所以理论上最终一定能触发返回但如果哪天面试题改成“不存在则返回-1”这个大小关系写错就会导致正确答案被漏判。细节决定成败这种地方我吃过亏。2.3 排序法一行代码背后的大坑排序法是我觉得最有戏剧性的一种解法。核心逻辑一句话排序后直接返回数组下标为 n/2 的那个元素。为什么因为多数元素出现次数超过了一半那么不管它出现在排序后数组的哪个位置中间位置一定被它占据。比如数组 [1, 2, 3, 4, 4, 4, 4]排序后是 [1, 2, 3, 4, 4, 4, 4]中间下标3是4正确。再比如 [2, 2, 2, 2, 3, 4, 5]排序后中间位置也还是2。这个洞察非常漂亮代码也极短public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length / 2]; }但这里有几个大坑。第一个坑Arrays.sort(int[]) 在Java里对基本类型数组使用的是双轴快排Dual-Pivot Quicksort平均O(n log n)在极端情况下某些采样策略可能会退化虽然实际中很少碰到。有人说“一行代码就O(n log n)了”这个复杂度你要心里有数。第二个坑排序法是原地修改了原数组如果后面还有代码需要用到原始顺序就会引入隐藏Bug面试时我建议先问清楚或者拷贝一份拷贝会带来额外空间。第三个坑也是最容易忽视的——如果题目不保证多数元素存在排序后取中间值直接返回是错的。比如 [1, 2, 3]中间下标1的值是2但2根本不是多数元素。所以排序法最吃“题目保证存在”这个前提。从工程角度我不太推荐在真实项目里用排序法解决类似问题因为排序的O(n log n)看着还行但相比Boyer-Moore的O(n)还是差了一个量级而且会破坏数据顺序。不过它作为面试中的“过渡答案”能展示你对排序特性的理解还是有价值的。3. Boyer-Moore投票算法面试官真正想看到的版本3.1 核心思想候选人机制与抵消逻辑我先把结论放在这里Boyer-Moore投票算法能在O(n)时间、O(1)空间内找到多数元素。它也是我面试时遇到这道题一定会给出的最终版本。这个算法的思想可以类比成一场擂台赛。数组里每个元素都是一个投票者它们支持各自阵营。我们维护两个变量candidate当前擂主和count擂主的净胜票数。遍历数组时遇到当前擂主的支持者count加1遇到反对者count减1当count变成0说明当前擂主被完全抵消掉了这时候把下一个元素推上擂台count重新置为1。这个“抵消”过程可以持续到数组末尾最后留在擂台上的就是多数元素。为什么最后留在擂台上的必然是多数元素因为多数元素的票数超过了总数的一半这意味着即便所有其他元素都联合起来死磕它也最多只能跟它打个平手不可能在抵消中把它清零。更严谨一点的直觉证明是非多数元素总数严格小于 n/2所以它们在抵消过程中必然全部耗尽而多数元素即使被各种针对最终也至少会留下一票正收益。这里我专门说明一下这个算法原理理解到“投票、抵消”层面就足够应付大多数场合了。如果面试官深入问证明可以用分组抵消的方式讲把每个非多数元素与一个多数元素配对抵消由于多数元素数量超过其他元素之和抵消之后必然有剩余的多数元素留下来。我在面试中用过这个解释反馈都还不错。3.2 正确性证明为什么最后留下的就是答案我想用更严谨但不枯燥的方式把正确性说清楚。设多数元素为x出现次数为 c其他元素总次数为 n-c。根据多数元素定义c n/2推出 c n-c也就是说多数元素比其他所有元素加起来还要多。现在看算法过程每执行一次count--都代表一个非candidate元素把一个candidate的票抵消掉。在这个过程中如果candidate恰好是x那么被抵消的是x的次数但最坏情况下“所有非多数元素都来抵消x”会消耗掉 n-c 次x的票因为 x 总共有 c 票c n-c所以x至少还剩 c - (n-c) 0 票没有被抵消。如果candidate不是x那么抵消过程只是消耗了非多数元素内部或某些非多数元素与x之间的差额更不会把x的整体优势消灭。所以无论如何x的净优势始终保留最后candidate必然落到x上。这个论证抓住了“剩余票数守恒”这个核心比死背证明舒服多了。这里有一个容易纠结的点如果count在中间变成0算法会更换candidate那之前的逻辑还成立吗成立。因为count归零意味着从上一轮candidate确立到当前位置这一段区间内投票全部中和了说明这一段里candidate的出现次数和非candidate元素一样多。把这一段整体扔掉不看剩下数组里仍然满足多数元素存在的条件因为x的出现次数仍然超过剩余长度的一半。所以算法可以安全地重新发起一轮擂台赛。这个“丢弃前缀”的视角也是很多证明的标准思路。3.3 Java实现与边界处理代码实现非常短我建议直接背下来但要能讲清楚每一步public int majorityElement(int[] nums) { int candidate 0; int count 0; for (int num : nums) { if (count 0) { candidate num; count 1; } else if (num candidate) { count; } else { count--; } } return candidate; }整个过程只有一次遍历没有额外数据结构空间复杂度稳定在O(1)。我习惯用if-else写逻辑清晰不推荐为了炫技写三元表达式嵌套可读性太差。边界情况这里也要注意。首先数组长度为1时循环里第一个元素就会成为candidatecount置1循环结束直接返回没问题。其次数组所有元素都相同candidate从头到尾不变count一直增加直接返回没问题。第三如果题目没有“保证存在多数元素”这个前置条件那循环结束时留在擂台上的candidate不一定真的是多数元素。比如数组 [1, 2, 3]算法走完candidate是3但3出现次数只有1并没有超过一半。这时候就需要第二阶段验证再遍历一遍数组统计candidate的实际出现次数如果大于n/2才返回否则返回-1或按题目要求返回特殊值。这个验证是O(n)所以整体时间复杂度仍然是O(n)。关于第二阶段验证我要多说一句。LeetCode 169主版本因为题目保证存在直接return candidate就够了。但很多面试官会故意把条件去掉考察你有没有意识到“摩尔投票只能保证找到潜在候选不能保证它就是多数元素”。我在模拟面试里见过不少候选人卡在这一步明明算法背得滚瓜烂熟却忘了在“不保证存在”的变体下需要二次扫描。所以建议不管题目怎么问心里都要有这个验证步骤的意识。4. 面试追问与避坑实录4.1 面试官角度从这道题能问出什么这道题在面试里属于“高频低门槛高延展”的题型。面试官问它表面上是考你会不会写代码实际上是看你能不能一步步从普通解走向最优解以及被追问时的反应。我模拟过几种追问链这里分享出来先写暴力解或哈希表解面试官问能不能降低空间复杂度这时候你顺势讲Boyer-Moore这就是一条非常漂亮的答题路径。写出Boyer-Moore后面试官问能证明它为什么正确吗这就是在考察算法理解深度能讲清“抵消后剩余票数守恒”就算合格。面试官问如果数组里可能不存在多数元素怎么办这就是考察边界意识回答要包含第二阶段验证。面试官问如果要求返回出现次数大于 n/3 的所有元素呢这是LeetCode 229摩尔投票的扩展版需要维护两个候选人、两个计数器。能答上来绝对是加分项。面试官还会顺带考Java基础HashMap的时间复杂度为什么平均O(1)、Integer缓存 -128到127的equals和问题、Arrays.sort的底层原理等。这些和本题高频绑在一起一道算法题可以串起一串Java八股文考点。这里我要专门说一下Integer缓存问题。如果改造成Integer[]数组HashMap计数时Integer的自动装箱可能命中缓存也可能不命中如果用 去比较两个Integer是否相等在-128到127范围外就会踩坑。这就是为什么算法题里对基本类型数组可以直接用 但一旦换成包装类数组就必须想清楚 equals 和 的区别。面试里这道题和Java基础结合得特别紧值得提前准备。4.2 常见错误与排查技巧我在刷题和帮人review代码时总结了几个高频错误。第一边界符号错误。多数元素的定义是“大于n/2”所以判断条件要写成 count n / 2。如果数组长度是奇数n/2向下取整比如n5多数元素至少要3次2次不满足所以 2 和 3 是等价的但n6时关键就是 3 而不是 3。用“ n / 2”最稳妥。第二Boyer-Moore最后不验证直接返回。主版本没问题但一旦题目变了就翻车。我自己的习惯是只要面试时口头确认一下“这里题目保证了存在多数元素所以不用二次验证”。第三HashMap计数时边遍历边返回但忘记处理null key。虽然这题是int数组不会有null但如果扩展到Integer[]Map.getOrDefault遇到null key时如果不小心容易埋下隐性问题。第四暴力解会有大量重复验证。外层循环里曾经作为候选检查过的值在后续遍历中又被当成新候选重新统计。可以引入一个去重集合跳过已经验证过的元素但这就引入了额外空间还不如直接上哈希表。这个对比反而说明哈希表方案在工程直觉上是更自然的。第五Arrays.sort会修改原数组如果后续代码依赖原始顺序容易引发偶发Bug。排查技巧其实很简单写一个测试类覆盖边界用例数组长度1[1]全部相同[2,2,2,2]一半以上[1,1,1,2,2]偶数长度多数元素出现在数组后半段负数参与 这样跑一遍基本能把绝大多数实现错误测出来。4.3 变体题与扩展思考这里我重点说LeetCode 229多数元素II。题目要求找出所有出现次数大于 n/3 的元素。注意一个事实出现次数大于n/3的元素最多只有2个因为3个都大于n/3的话总数就超过n了。这个“最多2个候选”的结论是扩展版能用两个candidate的前提。实现思路维护两个候选人和两个计数器遍历过程中用类似Boyer-Moore的抵消逻辑但规则变成遇到属于候选人的票就给它加票如果两个候选人都不是当前元素就同时给两个候选人减票如果某个候选人票数清零就用当前元素替代它。遍历结束后两个候选人只是“潜在的多数元素”必须再扫描一遍数组确认各自出现次数是否真的大于n/3。这个变体是面试进阶题能写出来并讲清楚的人很少一旦答出来很加分。扩展思考也可以往数据流方向走。Boyer-Moore是一个天然支持流式处理的算法因为每个元素只处理一次不需要回退也不需要存历史数据。比如线上服务日志里想要实时判断某个来源的访问量是否超过了流量的一半就可以用这个思路维护一个状态量。工程项目里虽然会直接用更复杂的Count-Min Sketch等算法但理解投票算法的场景能让你在系统设计面试里多一个谈资。5. 实战复盘与个人体会5.1 一套完整可跑的测试代码我把自己在本地验证这道题的测试代码贴一份可以直接复制到IDE里跑。这里顺便把“保证存在”和“不保证存在”两种逻辑都写进去方便对照。import java.util.Arrays; import java.util.HashMap; import java.util.Map; public class MajorityElementTest { static int boyerMoore(int[] nums) { int candidate 0; int count 0; for (int num : nums) { if (count 0) { candidate num; count 1; } else if (num candidate) { count; } else { count--; } } return candidate; } static int boyerMooreWithCheck(int[] nums) { int candidate boyerMoore(nums); int count 0; for (int num : nums) { if (num candidate) { count; } } return count nums.length / 2 ? candidate : -1; } public static void main(String[] args) { int[][] cases { {1}, {1, 1}, {2, 2, 1, 1, 1}, {3, 3, 3, 4}, {1, 2, 3} }; for (int[] nums : cases) { System.out.println(Arrays.toString(nums) - boyerMoore(nums)); System.out.println( withCheck: boyerMooreWithCheck(nums)); } } }注意最后一个用例 [1,2,3]boyerMoore返回的可能是3但3显然不是多数元素而boyerMooreWithCheck会返回-1。这个对比特别能说明“验证步骤”的必要性。我建议你在本地跑一下输出结果会非常直观。5.2 我个人的刷题体会最后说点实在的。多数元素这道题我在不同阶段刷过三次每一次感受都不一样。第一次是在刷题初期只会暴力解贴个AC就过去了第二次整理热题100专题时开始认真梳理5种解法和复杂度第三次是在准备面试时才发现这道题最值钱的部分藏在Boyer-Moore的证明和变体题里。我的体会是刷LeetCode不能只以AC为目标同样的题多问自己一句“这个解法为什么对”“能不能更好”收获会完全不同。实际工作中我也很少直接用投票算法去处理类似业务需求毕竟数据量不够大时HashMap是最直接的。但投票算法给了我一个很好的思维模型有些统计问题不一定需要完整记录每个计数利用“多数元素超过半数”这种结构性的约束可以用极小的状态量完成实时判定。这种思维在系统设计、流式计算、降采样等问题里都能迁移。如果让我给后来者一个建议那就是把每道热题都按“暴力解 - 常规解 - 最优解 - 证明 - 变体”这条链路过一遍。以多数元素为例你手里不只是多了一道题的答案而是多了一套通用的算法分析工具箱。下次见到“出现次数超过一半”“查找主元素”这类问题你会第一时间想到Boyer-Moore这就值了。