【剑指offer】出现次数超过一半的数字（python）

摩尔投票法 Boyer-Moore majority vote algorithm，时间O(n)空间O(1)
假如数组中存在众数，那么众数一定大于数组的长度的一半。
思想就是：如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数。

具体做法：

  1. 初始化：候选人cond = -1， 候选人的投票次数cnt = 0
  2. 遍历数组，如果cnt=0， 表示没有候选人，则选取当前数为候选人，++cnt
  3. 否则，如果cnt > 0, 表示有候选人，如果当前数=cond，则++cnt，否则--cnt
  4. 直到数组遍历完毕，最后检查cond是否为众数 
# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        majority = numbers[0]
        # 使用cnt统计元素出现次数，当遍历到的元素和统计元素相等时cnt++，否则cnt--
        # 如果查找了i个元素，且cnt==0，说明前i个元素没有majority，或者有majority但是出现次数小于i/2
        cnt = 1
        for i in range(len(numbers)):
            cnt = cnt + 1 if numbers[i]==majority else cnt - 1
            if cnt == 0:
                majority = numbers[i]
                cnt = 1
        cnt = 0
        for i in numbers:
            if i == majority: 
                cnt+=1
        # 最后检查cnt是否为众数
        return majority if cnt > len(numbers)//2 else 0