前言
新的一年，好好学习。
正文
问题来源
本问题来自leetcode上的229题。
问题描述
给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例 1：
输入: [3,2,3]
输出: [3]
示例 2：
输入: [1,1,1,3,3,2,2,2]
输出: [1,2]
分析：
此题和169题是一个思想
func majorityElement(nums []int) []int {
nx, ny, cx, cy := 0, 0, 0, 0
for _, n := range nums {
if nx == n {
cx++
} else if ny == n {
cy++
} else if cx == 0 {
nx = n
cx++
} else if cy == 0 {
ny = n
cy++
} else {
cx--
cy--
}
}
cx, cy = 0, 0
for _, n := range nums {
if n == nx {
cx++
} else if n == ny {
cy++
}
}
oneThird := len(nums) / 3
ret := make([]int, 0, 2)
if cx > oneThird {
ret = append(ret, nx)
}
if cy > oneThird {
ret = append(ret, ny)
}
return ret
}
用map存储会快（虽然要求空间复杂度为1）
func majorityElement(nums []int) []int {
stat, res, limit := map[int]int{}, []int{}, len(nums)/3
for _, num := range nums {
stat[num]++
}
for num, count := range stat {
if count > limit {
res = append(res, num)
}
}
return res
}
总结：
勤思考。
结语
不管怎么样好好加油。
