当前位置：首页 > news >正文

算法训练营第十二天| 169.多数元素

news 2026/4/25 16:15:10

今日任务：169. 多数元素尝试多种解法，提交第二周学习小结
题意：
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。
题目链接：https://leetcode.cn/problems/majority-element/
官方题解：https://leetcode.cn/problems/majority-element/solutions/146074/duo-shu-yuan-su-by-leetcode-solution/

思路：

一、基础思路

1. 哈希表统计法（最直观）

核心思想：遍历数组，用哈希表记录每个数字出现的次数，最后遍历哈希表，找到次数超过 n/2 的数字。

时间复杂度：O (n)（遍历两次数组）
空间复杂度：O (n)（需要哈希表存储元素）
优点：逻辑简单，一眼能看懂
缺点：占用额外空间，不满足进阶要求

2. 排序法（取巧简单）

核心思想：数组排序后，多数元素一定出现在数组中间位置（因为它超过一半长度）。比如数组长度 7，中间索引 3；长度 3，中间索引 1，排序后这个位置的数就是答案。

时间复杂度：O (n log n)（排序的时间）
空间复杂度：O (1) 或 O (n)（取决于排序算法）
优点：代码极简，一行排序 + 取中间值
缺点：时间复杂度不如最优解

二、进阶最优思路（满足 O (n) 时间 + O (1) 空间）

摩尔投票法（本题最佳解法）

核心思想：利用「多数元素数量 > 其他所有元素总和」的特性，通过投票抵消找到目标数。

初始化两个变量：候选人(candidate)和票数(count)，初始值都为 0
遍历数组每个元素：
- 如果票数count=0，把当前元素设为新候选人
- 如果当前元素 == 候选人，票数 + 1
- 如果当前元素！= 候选人，票数 - 1
遍历结束后，候选人就是多数元素

原理：多数元素的数量足够多，抵消完其他元素后，最终剩下的一定是它。

三、代码实现（最优：摩尔投票法）

def majorityElement(nums): # 初始化候选人和票数 candidate = 0 count = 0 for num in nums: # 票数为0，更换候选人 if count == 0: candidate = num # 投票：相同+1，不同-1 count += 1 if num == candidate else -1 return candidate

遇到的困难：

一、做题第一想法的阻碍

只会暴力思路一开始只能想到双层循环逐个统计次数，时间复杂度爆炸，完全没考虑数据范围（数组长度最大 5e4），暴力解法直接超时。
想不到哈希优化知道要统计次数，但想不到用字典 / 哈希表快速计数，只会手写统计，代码冗余、效率低。

二、普通解法的困难（哈希 / 排序）

哈希表细节易错

忘记初始化键值，导致 key 不存在报错；
遍历完字典后，不会快速筛选出「大于 n/2」的元素，判断条件写错。

排序法理解卡顿不能理解：为什么排序后中间下标一定是多数元素，逻辑想不通，只能死记结论，换题型就不会用。

三、进阶最大难点：摩尔投票法（最容易卡）

完全理解不了核心原理不懂「相互抵消」的逻辑，不明白为什么两两不同元素抵消，最后剩下的一定是众数。疑惑点：为什么别的元素不会残留？
流程逻辑混乱记不住执行步骤：count 为 0 才换候选人、相同 + 1、不同 - 1，手写代码时顺序写反、条件写错。
边界场景怀疑遇到负数、超长数组时，会怀疑算法失效，不敢确定结果一定正确。

四、通用代码层面困难

下标、长度计算错误混淆n/2和⌊n/2⌋，判断次数的条件写错。
忽略题目条件题目明确：一定存在多数元素，不需要额外校验，自己多写多余判断，增加代码负担。

五、整体思维困难

思维固化只会用「计数类」常规思路，缺少抵消、博弈、投票这类巧解思维，算法思维单一。
不会分析复杂度写完代码后，不会判断时间、空间复杂度，不知道哪种解法符合进阶要求。

（摩尔投票法）

int majorityElement(int* nums, int numsSize) { // 候选人 int candidate = 0; // 票数 int count = 0; for (int i = 0; i < numsSize; i++) { // 票数为0，更换候选人 if (count == 0) { candidate = nums[i]; } // 相同+1，不同-1 if (nums[i] == candidate) { count++; } else { count--; } } // 题目保证一定存在多数元素，直接返回 return candidate; }

今日收获：