229. Majority Element II

Medium
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 * 104
  • -109 <= nums[i] <= 109
Follow up: Could you solve the problem in linear time and in O(1) space?

解題

Runtime: 7 ms, faster than 98.21%
Memory Usage: 5 MB, less than 91.7%
func majorityElement(nums []int) []int {
m := make(map[int]int)
l := len(nums)
​
ans := make([]int, 0)
for _, num := range nums {
if m[num] <= l/3 && m[num]+1 > l/3 {
ans = append(ans, num)
}
m[num]++
}
​
return ans
}