LeetCode 229. 多数元素 II

Categories:

题目描述
思路分析
参考代码
相似题目

题目描述

🔥 229. 多数元素 II

思路分析

我们可以使用 摩尔投票法 的扩展版本来解决这个问题。具体思路如下：

候选人选择：我们可以维护两个候选元素和它们的计数器。

计数器更新：

遍历数组，对于每个元素：

如果当前元素等于第一个候选元素，增加第一个候选元素的计数。

如果当前元素等于第二个候选元素，增加第二个候选元素的计数。

如果当前元素不等于任何候选元素且两个计数器都不为零，则减少两个计数器。

如果两个计数器都为零，则将当前元素设为候选元素，并将计数器设为 1。

结果验证：遍历结束后，可能存在两个候选元素。需要再次遍历数组来确认它们的出现次数是否超过 n/3。

参考代码

// 找出出现次数超过 n/3 的元素
func majorityElement(nums []int) []int {
	if len(nums) == 0 {
		return []int{}
	}

	// 初始化候选元素和计数器
	candidate1, candidate2, count1, count2 := 0, 0, 0, 0

	// 第一遍遍历，找到候选元素
	for _, num := range nums {
		if num == candidate1 {
			count1++
		} else if num == candidate2 {
			count2++
		} else if count1 == 0 {
			candidate1, count1 = num, 1
		} else if count2 == 0 {
			candidate2, count2 = num, 1
		} else {
			count1--
			count2--
		}
	}

	// 第二遍遍历，确认候选元素的出现次数
	var res []int
	count1, count2 = 0, 0
	for _, num := range nums {
		if num == candidate1 {
			count1++
		} else if num == candidate2 {
			count2++
		}
	}

	if count1 > len(nums)/3 {
		res = append(res, candidate1)
	}
	if count2 > len(nums)/3 {
		res = append(res, candidate2)
	}

	return res
}

时间复杂度：O (n)，其中 n 是数组的长度。我们只遍历了数组两次。

空间复杂度：O (1)，只使用了常数级别的额外空间。

🍏 点击查看 Java 题解

write your code here

相似题目

LeetCode 169. 多数元素

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/58482309