Majority Element II

要点：无论是1个majority，2个majority还是k个，都是三种情况：count+1，all count-1，情况变化发生在0（初始或者减到0）。重要的是三种情况的验证顺序：首先cand已经存在，那么对应count+1，else：检查0，初始化，else：所有count--

这个算法的假设是如果有个数>n/k次存在，那么其他元素offset最多n/k次。所以增加只是对一个count，而减少对所有count。另外，当count-1到0的时候，并不是在同一个循环内reset，而是到下一个元素。因为2个元素势均力敌，并不应该立刻选第2个。当然这样如果不存在majority会有false positive，比如[2,2,2,3,4,5], k=1，2是不符合条件的。所以要最后再check一遍

错误点

• cand1和cand2初始值：用0和1，仅仅是为了让二者不同（否则有可能结果包括2次），因为最后有一轮额外check，所以不用担心值不符合条件
• / vs //: //是integer division而/是float division

class Solution(object):    def majorityElement(self, nums):        """        :type nums: List[int]        :rtype: List[int]        """        cand1, cand2 = 0,1        count1, count2=0,0        for i in nums:            if cand1==i:                count1+=1            elif cand2==i:                count2+=1            elif count1==0:                cand1=i                count1=1            elif count2==0:                cand2=i                count2=1            else:                count1-=1                count2-=1        return [n for n in [cand1, cand2] if nums.count(n)>len(nums)//3]