leetcode - 229. Majority Element II

Description

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]
1
2

Example 2:

Input: nums = [1]
Output: [1]
1
2

Example 3:

Input: nums = [1,2]
Output: [1,2]
1
2

Constraints:

1 <= nums.length <= 5 * 10^4
-10^9 <= nums[i] <= 10^9
1
2

Solution

Boyer-Moore Majority Vote, find the first 2 majorities, then check if they appear more than n/3 times.

For boyer-moore majority vote, if we want to find multiple majorities, use new element to decrease all previous counters.

Time complexity: $o(n)$
Space complexity: $o(1)$

Code

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        n1, c1, n2, c2 = 0, 0, 1, 0
        for each_num in nums:
            if each_num == n1:
                c1 += 1
            elif each_num == n2:
                c2 += 1
            elif c1 == 0:
                n1, c1 = each_num, 1
            elif c2 == 0:
                n2, c2 = each_num, 1
            else:
                c1 -= 1
                c2 -= 1
        c1, c2 = 0, 0
        for each_num in nums:
            if each_num == n1:
                c1 += 1
            elif each_num == n2:
                c2 += 1
        res = []
        if c1 > len(nums) / 3:
            res.append(n1)
        if c2 > len(nums) / 3:
            res.append(n2)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27