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

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

　　分析：数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现次数的和还要多。因此我们可以考虑在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为0，我们需要保存下一个数字，并把次数置1。

　　这里要注意的是，如果数组中没有出现次数超过数组长度一般的数的时候，此时遍历到最后，最后一个数的计数为1，返回这个数是明显不对的。因此可以考虑到如果数组中有最大的数的话有下面两种情况：

　　1、倒数第二个数的计数大于等于2；

　　2、倒数第二个数的计数等于1（前面的数中，出现次数超数组一半的数与其他数各占一半），并且最后一个数与倒数第二个数相等；

　　考虑到了这些情况便可写出如下代码：

 1 int MoreThanHalfNum_Solution(vector<int> numbers) {
 2         int maxNum = 0;
 3         if(numbers.empty())
 4             return maxNum;
 5         maxNum = numbers[0];
 6         int numCount = 1;
 7         for(int i=1;i<numbers.size()-1;i++){
 8             if(numbers[i] == maxNum){
 9                 numCount++;
10             }else{
11                 numCount--;
12                 if(numCount == 0){
13                     numCount = 1;
14                     maxNum = numbers[i];
15                 }
16             }
17         }
18         if((numCount == 1 && numbers.back() == maxNum)||numCount>1)
19             return maxNum;
20         else return 0;
21 }

　　结果的在线测试OJ系统：http://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tqId=11181&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking