面试题39：数组中出现次数超过一般的数字

题目：
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

思路一：
看到这个题目的第一个思路就是建立一个字典统计每个数字出现的次数，然后再将字典遍历一遍，当某个键值的value大于len(numbers)/2时，返回这个键值，否则返回0。这种思路需要额外的空间来辅助。

代码实现一：

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        #solution1 通过额外的字典空间来解决这个问题
        #特殊情况
        if len(numbers)<=0 or numbers == None:
            return 0

        SaveDicNum = {}  #保存次数的字典
        for num in numbers:
            if num in SaveDicNum.keys():
                SaveDicNum[num] +=1
            else:
                SaveDicNum[num] = 1

        for key in SaveDicNum.keys():
            if SaveDicNum[key] > (len(numbers)/2):
                return key
        return 0

思路二：(剑指offer的方法2)
因为该数字出现次数比其他所有数字出现的次数之和还要多，需要保存两个变量，一个是最后一次设置time为1的值res，另一个是time。当前值与res相同时time加1，不同时time减1，当time为0时，res设置为当前值，且time重置为1。要找的数字肯定是最后一次把次数设为1时对应的数字。最后再判断一下res值的出现次数是否大于一半即可。

代码实现二：

# -*-coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        if numbers == None or len(numbers) <=0:
            return 0
        
        res = numbers[0]  #初始化
        time = 1

        for i in range(1,len(numbers)):
            if time == 0:
                res = numbers[i]
                time =1
            elif numbers[i] == res:
                time +=1
            else:
                time -=1

        #验证
        temp = 0
        for i in range(len(numbers)):
            if numbers[i] == res:
                temp +=1

        if temp*2 > len(numbers):
            return res
        return 0

提交结果：

思路一结果 思路二结果