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

（一）题目描述

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

（二）思路分析

       假设在数组中出现的次数超过数组长度一半的数字为a，a出现的次数比其他所有数字出现的次数的和都要多。设用于存储a的整形变量res，一个用于存储a出现次数的整形变量count。res初始值为number[0]，count初始值为1。当遍历到下一个数组元素时，如果当前元素和res相同，则count+1，否则count-1。如果count=0，则保存下一个数字，并设置count=1.

（三）代码实现

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.size() == 0)
        {
            return 0;
        }
        else
        {
            int res = numbers[0];
            int count = 1;
            
            for(unsigned long int i=1; i<numbers.size(); i++)
            {
                if(res == numbers[i])
                {
                    count++;
                }
                else
                {
                    count--;
                }
                if(count == 0)
                {
                    res = numbers[i];
                    count = 1;
                }
            }
            count = 0;
            for(unsigned long int i=0; i<numbers.size(); i++)
            {
                if(numbers[i] == res)
                {
                    count++;
                }
            }
            if(count*2 > numbers.size())
            {
                return res;
            }
            else
            {
                return 0;
            }
        }
    }
};