229. 多数元素 II
229. 多数元素 II
🟠 Medium 🔖 数组
哈希表
计数
排序
🔗 力扣
LeetCode
题目
Given an integer array of size n
, find all elements that appear more than ⌊n/3⌋
times.
Example 1:
Input: nums = [3,2,3]
Output: [3]
Example 2:
Input: nums = [1]
Output: [1]
Example 3:
Input: nums = [1,2]
Output: [1,2]
Constraints:
1 <= nums.length <= 5 * 10^4
-10^9 <= nums[i] <= 10^9
Follow up: Could you solve the problem in linear time and in O(1)
space?
题目大意
给定一个大小为 n 的整数数组,找出其中所有出现超过 ⌊ n/3 ⌋
次的元素。
示例 1:
输入: nums = [3,2,3]
输出:[3]
示例 2:
输入: nums = [1]
输出:[1]
示例 3:
输入: nums = [1,2]
输出:[1,2]
提示:
1 <= nums.length <= 5 * 10^4
-10^9 <= nums[i] <= 10^9
进阶: 尝试设计时间复杂度为 O(n)
、空间复杂度为 O(1)
的算法解决此问题。
解题思路
由于出现次数大于 n/3
次的元素最多只有两个,因此可以利用摩尔投票法将问题简化为寻找最多两个候选人。
- 第一轮:找到可能的候选元素。 核心逻辑:对于出现次数超过
n/3
的元素,其在数组中的频次一定比其他元素更高。当遇到不属于现有候选人的数字时,减少候选人的计数,最终剩下的候选人是可能超过n/3
次的元素。
- 使用两个变量
candidate1
和candidate2
分别记录两个可能的候选人。 - 使用两个计数器
count1
和count2
分别记录这两个候选人的票数。 - 遍历数组:
- 如果当前数字等于
candidate1
,增加count1
。 - 如果当前数字等于
candidate2
,增加count2
。 - 如果
count1
为 0,设置当前数字为candidate1
,并将count1
置为 1。 - 如果
count2
为 0,设置当前数字为candidate2
,并将count2
置为 1。 - 如果当前数字与
candidate1
和candidate2
都不相同,则count1
和count2
同时减 1。
- 如果当前数字等于
- 第二轮:验证候选元素是否满足条件。
初始化两个计数器
count1
和count2
为 0。遍历数组:
- 如果当前数字等于
candidate1
,增加count1
。 - 如果当前数字等于
candidate2
,增加count2
。
- 如果当前数字等于
检查
count1
和count2
是否超过n/3
:- 如果
count1 > n/3
,将candidate1
加入结果。 - 如果
count2 > n/3
,将candidate2
加入结果。
- 如果
复杂度分析
- 时间复杂度:
O(n)
,两次遍历数组。 - 空间复杂度:
O(1)
,使用了常数个变量。
代码
/**
* @param {number[]} nums
* @return {number[]}
*/
var majorityElement = function (nums) {
const n = nums.length;
let candidate1 = null,
candidate2 = null;
let count1 = 0,
count2 = 0;
// 第一遍:摩尔投票法,找出两个候选者
for (let num of nums) {
if (candidate1 === num) {
count1++;
} else if (candidate2 === num) {
count2++;
} else if (count1 === 0) {
candidate1 = num;
count1 = 1;
} else if (count2 === 0) {
candidate2 = num;
count2 = 1;
} else {
count1--;
count2--;
}
}
// 第二遍:验证候选者
count1 = 0;
count2 = 0;
for (let num of nums) {
if (num === candidate1) count1++;
else if (num === candidate2) count2++;
}
const result = [];
if (count1 > Math.floor(n / 3)) result.push(candidate1);
if (count2 > Math.floor(n / 3)) result.push(candidate2);
return result;
};
:::
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
169 | 多数元素 | [✓] | 数组 哈希表 分治 2+ | 🟢 | 🀄️ 🔗 |
1150 | 检查一个数是否在数组中占绝大多数 🔒 | 数组 二分查找 | 🟢 | 🀄️ 🔗 | |
2404 | 出现最频繁的偶数元素 | 数组 哈希表 计数 | 🟢 | 🀄️ 🔗 |