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