229. Majority Element II

题目

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]

Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

题目大意

给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

解题思路

• 这一题是第 169 题的加强版。Boyer-Moore Majority Vote algorithm 算法的扩展版。
• 题目要求找出数组中出现次数大于 ⌊ n/3 ⌋ 次的数。要求空间复杂度为 O(1)。简单题。
• 这篇文章写的不错，可参考：https://gregable.com/2013/10/majority-vote-algorithm-find-majority.html

代码

package leetcode

// 解法一 时间复杂度 O(n) 空间复杂度 O(1)
func majorityElement229(nums []int) []int {
	// since we are checking if a num appears more than 1/3 of the time
	// it is only possible to have at most 2 nums (>1/3 + >1/3 = >2/3)
	count1, count2, candidate1, candidate2 := 0, 0, 0, 1
	// Select Candidates
	for _, num := range nums {
		if num == candidate1 {
			count1++
		} else if num == candidate2 {
			count2++
		} else if count1 <= 0 {
			// We have a bad first candidate, replace!
			candidate1, count1 = num, 1
		} else if count2 <= 0 {
			// We have a bad second candidate, replace!
			candidate2, count2 = num, 1
		} else {
			// Both candidates suck, boo!
			count1--
			count2--
		}
	}
	// Recount!
	count1, count2 = 0, 0
	for _, num := range nums {
		if num == candidate1 {
			count1++
		} else if num == candidate2 {
			count2++
		}
	}
	length := len(nums)
	if count1 > length/3 && count2 > length/3 {
		return []int{candidate1, candidate2}
	}
	if count1 > length/3 {
		return []int{candidate1}
	}
	if count2 > length/3 {
		return []int{candidate2}
	}
	return []int{}
}

// 解法二 时间复杂度 O(n) 空间复杂度 O(n)
func majorityElement229_1(nums []int) []int {
	result, m := make([]int, 0), make(map[int]int)
	for _, val := range nums {
		if v, ok := m[val]; ok {
			m[val] = v + 1
		} else {
			m[val] = 1
		}
	}
	for k, v := range m {
		if v > len(nums)/3 {
			result = append(result, k)
		}
	}
	return result
}

---