Hot 100 --- 多数元素

本文概览本文讲解多数元素多数元素出现次数超过 n/2所以排序后下标 n/2 的位置一定是它更优的摩尔投票法把问题看成两两抵消因为多数元素的总数超过其余元素之和抵消到最后剩下的就是它O(n) 时间、O(1) 空间一、题目二、题目分析1. 题目要求给定一个大小为n的数组nums返回其中的多数元素。多数元素是指在数组中出现次数大于⌊n / 2⌋的元素。可以假设数组是非空的并且给定的数组总是存在多数元素。示例 1nums [3, 2, 3]→ 3示例 2nums [2, 2, 1, 1, 1, 2, 2]→ 22. 怎么想这题题目要找一个出现次数最多的元素而且它有个很强的保证次数超过 n/2一半以上。这个超过一半是整个题的题眼围绕它能想出三种层次的解法老老实实数用哈希表把每个数出现几次统计出来谁超过 n/2 就返回谁。直观但要多花 O(n) 的空间。利用超过一半这个位置性质既然它占了一半以上把它排好序之后数组正中间那个位置是不是一定就是它顺着这个想法能省掉哈希表。再往深想一层过半意味着它比其他所有元素的总数还多。如果让元素两两抵消它是不是注定抵消不完、最后剩下来这就是摩尔投票法能做到 O(n) 时间、O(1) 空间。3. 需要解决哪几个问题问题一哈希表计数怎么实现为什么它拿不到O(1) 空间问题二为什么排序之后下标n/2的位置一定是多数元素怎么证明问题三核心摩尔投票法里那个抵消到底在干什么为什么多数元素抵消到最后一定剩得下三、方法一哈希表计数O(n) 空间1. 思路概览publicintmajorityElement(int[]nums){MapInteger,IntegercountnewHashMap();intnnums.length;for(intnum:nums){intccount.getOrDefault(num,0)1;count.put(num,c);if(cn/2){returnnum;// 已经超过一半可以直接返回}}return-1;}思路简要说明边扫边计数map里存这个数出现了几次随时检查每加一次就看看次数有没有超过n / 2超过就是答案时间复杂度 O(n)空间 O(n)2. 思路详解count.getOrDefault(num, 0)的意思是取出num当前的计数如果没有就当 0加 1 之后再写回 map。每写回一次就判断一下有没有过半。以[2, 2, 1, 1, 1, 2, 2]n 7一半是 3为例num2计数 2→1 num2计数 2→2 num1计数 1→1 num1计数 1→2 num1计数 1→3 num2计数 2→3 num2计数 2→4 3 → 返回 2 ✓思路没有绕弯唯一的问题是那个哈希表——最坏情况下要存下所有不同的数空间是 O(n)。题目没强制要求省空间但既然超过一半这个条件还能利用就值得往下想。3. 复杂度分析时间复杂度 O(n)遍历一次哈希操作均摊 O(1)。空间复杂度 O(n)哈希表最多存 n 个不同的键。四、方法二排序后取中间O(n log n)1. 思路概览publicintmajorityElement(int[]nums){Arrays.sort(nums);returnnums[nums.length/2];}思路简要说明先排序相同的元素会被排到一起直接取中间下标n / 2上的元素就是多数元素时间复杂度 O(n log n)空间 O(1)不算排序本身的开销2. 思路详解为什么中间那个位置一定是多数元素设多数元素为m它出现了c次题目保证c n / 2也就是c ≥ ⌊n/2⌋ 1。排好序之后所有等于m的元素会连成一整块占据一段连续的位置。用反证法假设下标n/2那个位置上不是m那说明m那一整块要么整个在它左边、要么整个在它右边。如果整块都在下标n/2的左边那它最多只能占据前⌊n/2⌋个位置也就是c ≤ ⌊n/2⌋和c ≥ ⌊n/2⌋ 1矛盾如果整块都在右边同理最多也只能占⌊n/2⌋个位置同样矛盾。两边都不可能所以下标n/2上只能是m。拿[2, 2, 1, 1, 1, 2, 2]看排序后是[1, 1, 1, 2, 2, 2, 2]n 7n / 2 3下标 3 上正好是2✓。这个方法的巧妙之处在于它压根不用知道每个数出现几次只靠过半 ⇒ 必然霸占中间位置这一条性质就够。代价是排序要 O(n log n)比线性慢。3. 复杂度分析时间复杂度 O(n log n)排序占主要开销。空间复杂度 O(1)只用了下标。五、方法三摩尔投票法O(n) 时间 O(1) 空间1. 思路概览publicintmajorityElement(int[]nums){intcandidatenums[0];intcount0;for(intnum:nums){if(count0){candidatenum;// 前面的都被抵消光了换这个数当候选人count1;}elseif(numcandidate){count;// 支持票 1}else{count--;// 反对票抵消掉一张支持票}}returncandidate;}思路简要说明维护一个候选人candidate是当前领先的那个数count是它的净票数遇到相同的就 1遇到不同的就 −1净票数归零就换人说明候选人被抵消光了让下一个数上台最后剩下的就是多数元素时间复杂度 O(n)空间 O(1)2. 思路详解第一步把问题看成互相抵消多数元素出现次数超过 n/2也就是说它的个数比其余所有元素加起来还多。这句话很容易被忽略但它是整个方法的根基。既然它一方人马比其他所有人加起来还多那就让不同阵营的元素两两抵消——每抵消掉一个多数元素也必然要搭上一个别的元素。就算把其他元素全部拿去和它拼掉它也还剩得下因为它的总数本来就更多。所以抵消到最后场上剩下的只能是它。第二步candidate和count在记录什么代码把上面这个过程压缩成了两个变量candidate当前占上风的那个元素count它手里还剩多少净票支持它的数量减去被反对掉的。遍历时的三种动作遇到和candidate相同的数→ 是自己人count遇到和candidate不同的数→ 换掉一个count--一票支持被一票反对抵消count减到 0→ 说明前面攒的票全被抵消光了candidate已经名存实亡。这时让当前这个数当新候选人count 1重新开始。为什么归零时可以放心换人因为count归零意味着从开头到现在这一段支持票和反对票正好打成平手整段全抵消了。这一段既然能自我消化干净把它整个丢掉也不影响剩下的部分——后面那些数的谁更多的格局和前面这一段的抵消结果无关。所以可以放心从那一位重新开始数。第三步完整执行过程以[2, 2, 1, 1, 1, 2, 2]答案是 2为例num2count0 → candidate2, count1 ← 2 上台 num2 candidate → count2 ← 又来一个自己人 num1! candidate → count1 ← 1 抵消掉一张票 num1! candidate → count0 ← 又抵消一张2 被拼光了 num1count0 → candidate1, count1 ← 1 上台 num2! candidate → count0 ← 2 把 1 拼光 num2count0 → candidate2, count1 ← 2 再次上台 返回 candidate 2 ✓再看示例 1 的[3, 2, 3]num3count0 → candidate3, count1 num2! → count0 num3count0 → candidate3, count1 返回 3 ✓可以留意到中间candidate换成过 1也归零过好几次但最后站着的还是 2——因为多数元素总数最多抵消到最后剩下的一定是它。中间那些起伏只是还没分出胜负的临时状态。第四步代码细节count 0时统一处理这个分支同时兼顾了数组第一个元素初始count 0第一个数自然上台和候选人被拼光后换人不用给第一个元素单独写逻辑。最后不需要再验证题目保证多数元素一定存在所以循环结束时candidate必然是答案。如果题目不保证就得再扫一遍数组确认它真的过半。count的含义要记准它不是候选人出现的总次数而是净票数中途被抵消掉的票已经从里面扣掉了。3. 复杂度分析时间复杂度 O(n)一次遍历每个元素常数次比较。空间复杂度 O(1)只有candidate和count两个变量。六、总结方法时间空间关键点哈希表计数O(n)O(n)直接统计每个数的出现次数排序取中间O(n log n)O(1)过半 ⇒ 必然占据下标n/2摩尔投票法O(n)O(1)过半 ⇒ 抵消不完最后剩的必是它三种方法一层比一层省共同的基础都是题目那句出现次数大于 ⌊n/2⌋老老实实计数是把过半交给哈希表去判断排序取中间是把过半翻译成位置性质——它必然霸占正中间摩尔投票是把过半翻译成数量对比——它比其余所有元素加起来还多所以两两抵消之后它一定还在。面试里最常被追问的是摩尔投票法重点不在代码就那么几行而在于能不能说清为什么抵消到最后剩下的就是多数元素这一点。