0229.md

title	description	keywords
229. 多数元素 II	LeetCode 229. 多数元素 II题解，Majority Element II，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 229. 多数元素 II 多数元素 II Majority Element 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 次的元素。

1. 使用两个变量 candidate1 和 candidate2 分别记录两个可能的候选人。
2. 使用两个计数器 count1 和 count2 分别记录这两个候选人的票数。
3. 遍历数组：
   • 如果当前数字等于 candidate1，增加 count1。
   • 如果当前数字等于 candidate2，增加 count2。
   • 如果 count1 为 0，设置当前数字为 candidate1，并将 count1 置为 1。
   • 如果 count2 为 0，设置当前数字为 candidate2，并将 count2 置为 1。
   • 如果当前数字与 candidate1 和 candidate2 都不相同，则 count1 和 count2 同时减 1。

• 第二轮：验证候选元素是否满足条件。

1. 初始化两个计数器 count1 和 count2 为 0。

2. 遍历数组：

   • 如果当前数字等于 candidate1，增加 count1。
   • 如果当前数字等于 candidate2，增加 count2。

3. 检查 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	出现最频繁的偶数元素		数组 哈希表 计数	🟢	🀄️ 🔗