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

题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

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

解法一：简易解法，低效
题解：我们可以先对整个数组进行排序，当排好序以后，如果解存在，则需要的那个数一定就在中间的位置，因为它的个数已经超过了整个数组的一半。如果解不存在就按题意返回0

    int MoreThanHalfNum_Solution(vector<int> numbers) {
        //第一部分:判断代码的鲁棒性
        if(numbers.empty()){
            return 0;
        }
        // 第二部分：对数组进行排序，并取出中间的数字
        sort(numbers.begin(),numbers.end());
        int middle = numbers[numbers.size()/2];
        // 第三部分：判断中间的数字出现的次数
        int count = 0;
        for(int i = 0;i<numbers.size();++i){
            if(numbers[i] == middle){
                ++count;
            }
        }
        // 第四部分：如果超过一半则返回中间的数字，否则返回0
        if(count > numbers.size()/2){
            return middle;
        }else{
            return 0;
        }
    }

代码框架：大致可以分为四个部分1.判断数组是否有；2取出排序后中间的数字；3.计算中间数字在整个数组出现的次数，4.最后判断次数是否大于整个数组长度的一半。

注意：由于用到了sort函数，所以它的时间复杂度肯定不会满足面试官的要求，那么就得要寻找更快速的解法。

解法二：高效遍历
这个和解法一有相似之处，都是先把最有可能满足题意要求的数字保存起来，然后在最后判断它是否满足要求，如果满足就返回它的值，如果不满足就返回0，但是它比解法一高效的地方在于没有排序，直接进行的遍历。

方法：我们在遍历数组的时候，保存两个值，一个是数组中的数字，另一个是次数，当遍历到下一个数字的时候，如果和上一次的数字一样则次数加1，如果不一样次数减一(相当于抵消了)，如果次数为0了，那就保存下一个数字，并把次数设置为1，因为我们要找的数字如果存在最后一定是把次数设置为1的那个数。

    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.empty()){
            return 0;
        }
        int temp = numbers[0];
        int time = 1;
        //[1,2,3,2,4,2,5,2,3]
        for(int i = 1;i<numbers.size();++i){
            if(time == 0){
                temp = numbers[i];
                time = 1;
            }else if(temp == numbers[i]){
                ++time;
            }else{
                --time;
            }
        }
        // 判断 temp 是否符合要求
        int count = 0;
        for(int i = 0;i<numbers.size();++i){
            if(temp == numbers[i]){
                ++count;
            }
        }
        if(count > numbers.size()/2){
            return temp;
        }else{
            return 0;
        }
    }

解法三：python 低效解法
以下是python 懒人解法,pyhton 时间复杂复很大，效率太低了，有个好处就是简便！

import collections
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        tmp = collections.Counter(numbers)
        x = len(numbers)/2
        for k, v in tmp.items():
            if v > x:
                return k
        return 0

代码解释：
第 4 行：建立一个映射字典的关系
Counter({2: 4, 1: 1, 3: 1, 4: 1})
第六行：k 代表的是 key ,v 代表的是 value ;
所以如果 v 大于 x 的话则返回 k ，如果循环出来就说明没有符合的值，则返回0