29、数组中出现次数超过一半的数字

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

首先想到的是用排序数组，然后看中间的数出现次数是不是超过数组长度的一半，超过则返回，不超过则输出0.

但是排序的时间复杂度是O(nlogn)，面试官可能不满意。因此想到用别的方法。

解法一，基于快排的partition函数，再构造地规划函数，比较繁琐，有兴趣的可以直接搜剑指offer的29题的解法。

解法二：

注意，无论哪一种解法， 都要判断数组是不是有效的。
对于最终返回的结果，需要再用数组做一次判断，判断该结果是不是在数组中出现次数超过了一半。

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        #从第一个数字开始，保存两个变量，一个数字，一个次数
        if len(numbers) == 0:
            return 0
        if len(numbers) == 1:
            return numbers[0]
        #第一个数字初始化为1
        num = numbers[0]
        times = 1
        for num_new in numbers[1:]:
            if times > 0:
                #若数字相同，便把tiems加1
                if num == num_new:
                    times += 1
                #若数字不相同，则把times减1
                else:
                    times -= 1
            #若次数变为0 ，则把下一个遇到的数字出现次数初始化为1
            else:
                num = num_new
                times = 0

        #判断这个数组，是不是有效的
        #对于num，此时在数组中出现的次数应该超过数组长度的一半.
        #OJ不能引用包。。。只能手动了
        n = 0
        for i in numbers:
            if i == num:
                n += 1
        
        #注意是超过一半，是大于，不包括等于
        if n > len(numbers)//2:
            return num
        else:
            return 0