Leetcode229.Majority element

給定一個大小為 n 的數組，找出其中所有出現超過 

⌊ n/3 ⌋

 次的元素。

說明: 要求算法的時間複雜度為 O(n)，空間複雜度為 O(1)。

輸入:[3,2,3]

輸出:[3]

摩爾投票法是對于任意多的候選人中選出一定部分的人，如果票不同則互相抵消掉，如果票相同則增加這個候選人的可抵消票數。

如果票數至少超過了一般的票數，則候選人中最多選取一個代表，

如果票數至少超過1/3的票數，則候選人中最多選取兩個代表

如果票數至少超過了1/m+1的票數，則候選人中最多選區m個代表

摩爾投票法分為兩個階段：抵消階段和計數階段

def majorityElement(nums):
    # ans = []
    # cnt = collections.Counter(nums)
    # count = len(nums)/3  #使用内置方法統計數組中的個數并以字典的形式表示
    #
    # for k,v in cnt.items():
    #     if v >count:
    #         ans.append(k)
    # return ans
    num1 = 0
    num2 = 0
    count1 = 0
    count2 = 0
    for i in nums:
        if i == num1:
            count1 += 1
        elif i == num2:
            count2 += 1
        elif count1 == 0:
            num1 = i
            count1 = 1
        elif count2 == 0:
            num2 = i
            count2 = 1
        else:
            count1 -= 1
            count2 -= 1 #抵消階段
    
    ​​​​​​​result = []
    count1, count2 = 0, 0
    for j in nums:
        if j == num1:
            count1 += 1
        elif j == num2:
            count2 += 1
    if count1 > len(nums) // 3:
        result.append(num1)
    if count2 > len(nums) // 3:
        result.append(num2)#計算階段
    return result