题解 | #数组中出现次数超过一半的数字# 投票法

#coding:utf-8
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numbers int整型一维数组 
# @return int整型
#
class Solution:
    def MoreThanHalfNum_Solution(self , numbers ):
        # write code here
        # 算法步骤：我们选择输入数组中第一个元素作为候选元素candidate，
        # 并设置其出现次数为count=1。随后遍历数组。当遇到与candidate相同的元素，
        #count+1;不同的元素，count-1。当count为0的时候，选择下一个元素为候选元素，
        #并且置count=1。遍历到数组的最后，剩下的candidate就是要求的结果
        #Step1: 找众数
        can = -1
        cnt = 0
        n = len(numbers)
        for i in range(0, n):
            if cnt == 0:
                can = numbers[i]
                cnt += 1
            else:
                if can == numbers[i]:
                    cnt += 1
                else:
                    cnt -= 1
        print ("Can: ", can)
        #Step2: 判断是否超过一半
        cnt = 0
        for i in range(0, n):
            if numbers[i] == can:
                cnt += 1
        if cnt > n // 2:
            return can
        return 0