E-169. Majority Element

E

O(n), O(n):

'''
    loop 1: 用dict存num和频率
    loop 2: 找出频率 > 指定值的num.
'''
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        freq_map={}
        max_freq=len(nums)//2    
        for num in nums:
            freq_map[num] = freq_map.get(num,0) + 1
        
        for num,freq in freq_map.items():
            if freq > max_freq:
                return num

'''
    稍微改进了一点,但是复杂度没变的方法:
    如果当前freq大于指定值, 立即返回
'''
# one pass + dictionary
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        freq_map={}
        max_freq=len(nums)//2
        for num in nums:
            freq_map[num] = freq_map.get(num,0) + 1
            if freq_map[num]> max_freq:
                return num

O(n), O(1):

A Linear Time Majority Vote Algorithm(仅仅当有存在超过半数的num为同一值时)

Majority Voting Algorithm

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cand, count = 0, 0
        for num in nums:
            if count == 0:
                cand, count = num,1
            elif num == cand:
                count += 1
            elif num != cand:
                count -= 1
        
        return cand