每日算法练习：LeetCode 169. 多数元素 ✅

大家好我是你们的算法小伙伴。今天我们来练习一道经典的数组问题 ——LeetCode 169. 多数元素它的最优解法「摩尔投票法」非常巧妙是面试中的高频考点。题目描述给定一个大小为n的数组nums返回其中的多数元素。多数元素是指在数组中出现次数大于⌊ n/2 ⌋的元素。你可以假设数组是非空的并且给定的数组总是存在多数元素。示例 1输入nums [3,2,3] 输出3示例 2输入nums [2,2,1,1,1,2,2] 输出2提示n nums.length1 n 5 * 10^4-10^9 nums[i] 10^9输入保证数组中一定有一个多数元素进阶尝试设计时间复杂度为 O (n)、空间复杂度为 O (1) 的算法解决此问题。解题思路方法一哈希表统计直观但空间复杂度高遍历数组用哈希表记录每个元素的出现次数最后遍历哈希表找到出现次数大于 n/2 的元素。时间复杂度O (n)空间复杂度O (n)方法二排序取中间元素利用多数元素特性因为多数元素出现次数大于 n/2所以排序后数组中间位置的元素一定是多数元素。时间复杂度O (n log n)空间复杂度O (1)若使用原地排序方法三摩尔投票法最优解这是题目进阶要求的 O (n) 时间、O (1) 空间解法核心思想是抵消不同元素也是我们重点要讲解的方法。核心前提题目明确保证数组中一定存在多数元素且出现次数 n/2。这意味着多数元素的数量 所有其他元素的数量之和这是摩尔投票法能生效的根本 —— 它的 “票数” 永远无法被完全抵消。通俗类比理解我们可以把这个过程想象成一场 “候选人对抗赛”数组里的每个元素都是一个 “候选人”互相 “投票对抗”多数元素的支持者足够多哪怕和所有其他候选人对抗最后剩下的也一定是它count就是当前候选者的净胜票数遇到和自己一样的元素 → 净胜票 1支持者增加遇到不一样的元素 → 净胜票 - 1互相抵消净胜票为 0 时 → 说明当前候选者的票数被完全抵消换当前元素当新候选。算法步骤初始化选数组第一个元素为初始候选candidate计数器count 1从第二个元素开始遍历数组若当前元素等于candidate→count若当前元素不等于candidate→count--若count 0→ 更新candidate为当前元素重置count 1遍历结束后candidate就是多数元素。代码实现class Solution { public int majorityElement(int[] nums) { // 1. 初始化选第一个元素当初始候选初始净胜票为 1 int candidate nums[0]; int count 1; // 2. 从第二个元素开始遍历第一个已作为候选 for (int i 1; i nums.length; i) { if (nums[i] candidate) { // 情况1遇到和候选相同的元素 → 净胜票1 count; } else { // 情况2遇到不同元素 → 净胜票-1互相抵消 count--; // 情况3净胜票为 0 → 候选者被完全抵消换当前元素当新候选 if (count 0) { candidate nums[i]; count 1; } } } // 3. 遍历结束剩下的候选就是多数元素 return candidate; } }代码逐行拆解初始化candidate nums[0]先假设第一个元素是候选count 1表示它有 1 票领先遍历逻辑相同元素增强当前候选的领先优势不同元素消耗当前候选的票数实现 “抵消”票数清零说明当前候选的优势耗尽更换新候选重新开始计数结果保证因为多数元素数量 其他元素总和所以它永远无法被完全抵消最终一定会成为最后剩下的候选。实例模拟验证我们以nums [2,2,1,1,1,2,2]多数元素是 2出现 4 次n743.5为例全程模拟执行过程表格遍历位置 (i)当前元素candidate (候选)count (净胜票)执行逻辑初始化-21选第一个元素 2 当候选初始票 1i1222和候选相同净胜票 1i2121和候选不同净胜票 - 1抵消 1 票i3120和候选不同净胜票 - 1 → 变为 0i4111count0 → 换候选为 1重置票 1i5210和候选不同净胜票 - 1 → 变为 0i6221count0 → 换候选为 2重置票 1遍历结束-21返回候选 2正确结果复杂度分析时间复杂度O (n)。仅需遍历数组一次执行 n-1 次操作。空间复杂度O (1)。仅使用两个变量存储候选和计数器无额外空间开销。总结这道题的核心魅力在于摩尔投票法它完美利用了「多数元素出现次数超过一半」的特性在不借助额外空间的情况下通过简单的计数与抵消操作高效找到结果。这种思想在处理「寻找出现次数超过 1/k 的元素」等进阶问题时也有重要应用是算法面试中必须掌握的经典技巧。今天的每日算法练习就到这里我们明天再见