题目描述

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

思路

将数组进行排序，然后遍历这个数组；
定义一个count用于计数，定义一个pre用于保存前一个数字；
若当前数等于前一个数，count++；
若当前数不等于前一个数，则重置count，这里直接置为1(有先归0再++的含义)，并且将pre更新；
比较count和half值，若大于，就返回当前数
遍历结束后，直接返回0(如果遍历结束跳出循环了，说明没有个数大于一半的)
注意：一开始没有考虑只有1个元素的情况，1个元素也应该满足题意的，直接返回numbers[0]

这里没有想到一个快捷方法：排完序后，如果存在个数超过一半的，那么这个数一定是中间的一个，这样只需要数一下数组中中间数的个数就可以了。

代码

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.size()<=0)
            return 0;
        if(numbers.size()==1)
            return numbers[0];
        int half_len=numbers.size()/2;
        for(int i=0;i<numbers.size()-1;i++) //将数组按照从小到大的顺序进行排序
        {
            int temp=0;
            for(int j=0;j<numbers.size()-i-1;j++)
            {
                if(numbers[j]>numbers[j+1])
                {
                    temp=numbers[j];
                    numbers[j]=numbers[j+1];
                    numbers[j+1]=temp;
                }
            }
        }
        int count=1;  //记录当前数字的个数
        int pre=numbers[0];   //存储前一个数字，用于与当前数字进行比较
        for(int i=1;i<numbers.size();i++)
        {
            if(pre!=numbers[i])   //若当前数不等于前一个，则清空count(这里就直接等于1了，把它自己算上了)，更新前一个数
            {
                count=1;
                pre=numbers[i];
            }
            else
                count++;
            if(count>half_len)
                return numbers[i];
        }
        return 0;
    }
};