Question

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]

Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

Solution

Use modified Boyer-Moore algorithm. There are at most two majority elements, and the number of non-majority elements must be fewer than either of them. Thus, we can maintain two counters. If a number equals to one of the candidates, the corresponding counter +1 while the other does not change; if a number does not equal to either of them, both counters -1. If a counter is 0, replace the candidate with the next number. At the end, verify both of them occurred more than ⌊ n/3 ⌋ times, because some times there is only one majority element.

The overall time complexity is \(O(n)\) (one pass for finding the majority candidates, and one pass for verification).

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if len(nums) == 0:
            return []
        elif len(nums) == 1:
            return nums

        candidate1, candidate2, count1, count2 = 0, 1, 0, 0

        for n in nums:
            if n == candidate1:
                count1 += 1
            elif n == candidate2:
                count2 += 1
            elif count1 == 0:
                count1 = 1
                candidate1 = n
            elif count2 == 0:
                count2 = 1
                candidate2 = n
            else:
                count1 -= 1
                count2 -= 1

        return [n for n in (candidate1, candidate2) if nums.count(n) > len(nums) // 3]