229. Majority Element II

Given an integer array of size n, find all elements that appear more than n/3 times. The algorithm should run in linear time and in $O(1)$ space.

Solution:

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        num1 = num2 = None
        count1 = count2 = 0
        for num in nums:
            if num == num1:
                count1 += 1
            elif num == num2:
                count2 += 1
            elif count1 == 0:
                num1 = num
                count1 += 1
            elif count2 == 0:
                num2 = num
                count2 += 1
            else:
                count1 -= 1
                count2 -= 1

        return [num for num in num1, num2
                if nums.count(num) > len(nums) / 3]

Related:

• 169. Majority Element