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.
Input: [3,2,3] Output: 
Input: [1,1,1,3,3,2,2,2] Output: [1,2]
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]