Majority Element

169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Boyer-Moore Voting Algorithm

利用一個count 計算candidate and non-candidate 出現次數。當為0時切換candidate. Array的 pre candidate count不重要, suffix candidate is sufficient

[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7] => 7
[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 5, 5, 5, 5] => 5

Source

def majorityElement(self, nums: List[int]) -> int:
    count = 0
    cand = None
    
    for n in nums:
        if count == 0:
            cand = n
        count += 1 if cand == n else -1
        
    return cand

229. Majority Element II

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.

"""
if condition先後次序重要, 先判斷cand1, cand2 exist
"""
def majorityElement(self, nums: List[int]) -> List[int]:
    cand1, cand2 = None, None
    count1, count2 = 0, 0
    
    for n in nums:
        if n == cand1:
            count1 += 1
        elif n == cand2:
            count2 += 1
        elif count1 == 0:
            cand1 = n
            count1 = 1
        elif count2 == 0:
            cand2 = n
            count2 = 1
        else:
            count1 -= 1
            count2 -= 1
            
    return [x for x in (cand1, cand2) if nums.count(x) > len(nums) // 3]