229.M 多数元素 II

Problem: 229. 多数元素 II

思路

摩尔投票法扩展

核心思想：对拼消耗，但这次我们需要维护两个候选者。由于出现次数超过 n/3 的元素最多只有2个，我们使用两个候选数和两个计数器。

• 第一遍遍历：找出可能的候选数

• 第二遍遍历：验证候选数是否真的超过 n/3

Code

func majorityElement(nums []int) []int {
	element1 := 0
	vote1 := 0
	element2 := 0
	vote2 := 0
	for _, num := range nums {
		if vote1 > 0 && num == element1 {
			vote1++
		} else if vote2 > 0 && num == element2 {
			vote2++
		} else if vote1 == 0 {
			element1 = num
			vote1 = 1
		} else if vote2 == 0 {
			element2 = num
			vote2 = 1
		} else {
			vote1--
			vote2--
		}
	}

	count1, count2 := 0, 0
	for _, num := range nums {
		if num == element1 {
			count1++
		} else if num == element2 {
			count2++
		}
	}

	var ans []int
	if vote1 > 0 && count1 > len(nums)/3 {
		ans = append(ans, element1)
	}
	if vote2 > 0 && count2 > len(nums)/3 {
		ans = append(ans, element2)
	}

	return ans
}