https://www.iteye.com/blog/mabusyao-2223195

摩尔投票法的基本思想很简单，在每一轮投票过程中，从数组中找出一对不同的元素，将其从数组中删除。这样不断的删除直到无法再进行投票，如果数组为空，则没有任何元素出现的次数超过该数组长度的一半。如果只存在一种元素，那么这个元素则可能为目标元素。

• ps：那么有没有可能出现最后有两种或两种以上元素呢？

  根据定义，这是不可能的，因为如果出现这种情况，则代表我们可以继续一轮投票。因此，最终只能是剩下零个或一个元素。

在算法执行过程中，我们使用常量空间实时记录一个候选元素c以及其出现次数f(c)，c即为当前阶段出现次数超过半数的元素。根据这样的定义，我们也可以将摩尔投票法看作是一种动态规划算法。

程序开始之前，元素c为空，f(c)=0。遍历数组A：

• 如果f(c)为0，表示截至到当前子数组，并没有候选元素。也就是说之前的遍历过程中并没有找到超过半数的元素。那么，如果超过半数的元素c存在，那么c在剩下的子数组中，出现次数也一定超过半数。因此我们可以将原始问题转化为它的子问题。此时c赋值为当前元素, 同时f(c)=1。
• 如果当前元素A[i] == c, 那么f(c) += 1。(没有找到不同元素，只需要把相同元素累计起来)
• 如果当前元素A[i] != c，那么f(c) -= 1 (相当于删除1个c)，不对A[i]做任何处理(相当于删除A[i])

如果遍历结束之后，f(c)不为0，则找到可能元素。

再次遍历一遍数组，记录c真正出现的次数，从而验证c是否真的出现了超过半数。上述算法的时间复杂度为O(n)，而由于并不需要真的删除数组元素，我们也并不需要额外的空间来保存原始数组，空间复杂度为O(1)。

def majorityElement(self, nums):
    cnt, cur = 0, -1
    for n in nums:
        if cnt == 0:
            cur = n
            cnt += 1
        else:
            if cur != n:
                cnt -= 1
            else:
                cnt += 1
    
    if cnt <= 0:
        return -1
    cnt = 0
    for n in nums:
        if n == cur:
            cnt += 1

    return cur if cnt > len(nums) / 2 else -1