跳至主要內容

229. 多数元素 II


229. 多数元素 II

🟠 Medium  🔖  数组 哈希表 计数 排序  🔗 力扣open in new window LeetCodeopen in new window

题目

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. 使用两个变量 candidate1candidate2 分别记录两个可能的候选人。
  2. 使用两个计数器 count1count2 分别记录这两个候选人的票数。
  3. 遍历数组:
    • 如果当前数字等于 candidate1,增加 count1
    • 如果当前数字等于 candidate2,增加 count2
    • 如果 count1 为 0,设置当前数字为 candidate1,并将 count1 置为 1。
    • 如果 count2 为 0,设置当前数字为 candidate2,并将 count2 置为 1。
    • 如果当前数字与 candidate1candidate2 都不相同,则 count1count2 同时减 1。
  • 第二轮:验证候选元素是否满足条件。
  1. 初始化两个计数器 count1count2 为 0。

  2. 遍历数组:

    • 如果当前数字等于 candidate1,增加 count1
    • 如果当前数字等于 candidate2,增加 count2
  3. 检查 count1count2 是否超过 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+🟢🀄️open in new window 🔗open in new window
1150检查一个数是否在数组中占绝大多数 🔒数组 二分查找🟢🀄️open in new window 🔗open in new window
2404出现最频繁的偶数元素数组 哈希表 计数🟢🀄️open in new window 🔗open in new window