Leetcode 229. Majority Element II

https://leetcode.com/problems/majority-element-ii/

Remember Majority Element one? In that problem, only one number can occur over n/2 times, and we solve it by +1 when it occurs and -1 when others occur, when count value equals 0 we change to the next number and set count 1, so in the end the current number is what we want.

So can we use the same thought here? For n/3, there will be at most two such numbers. Hence we can play the exactly same trick again, while this time there are two numbers.

Solution:

# T:O(n) S:O(1)
class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n1 = n2 = None
        c1 = c2 = 0
        for num in nums:
            if n1 == num:
                c1 += 1
            elif n2 == num:
                c2 += 1
            elif c1 == 0:
                n1, c1 = num, 1
            elif c2 == 0:
                n2, c2 = num, 1
            else:
                c1, c2 = c1 - 1, c2 - 1
        size = len(nums)
        return [n for n in (n1, n2) 
                   if n is not None and nums.count(n) > size / 3]

Run Time: 64 ms