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
}