题目描述

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

解题思路

1. 将数组排序。若是数组中有一个数字出现的次数超过数组长度的一半，那么数组排序后，这个数字也必定出如今数组的中间位置；
2. 因此第二步，咱们按当前有序的顺序遍历整个数组，若是和中间元素的数值相同，计数+1，最后比较计数是否大于数组长度的一半就能够了

代码实现

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.empty())
            return 0;
        
        sort(numbers.begin(), numbers.end());
        int mid = numbers[numbers.size() / 2];
        int count = 0;
        for(int i = 0; i < numbers.size(); i++){
            if(numbers[i] == mid)
                count++;
        }
        return (count > numbers.size() / 2)?mid:0;
    }
};

运行结果

运行时间：3ms
占用内存：484k数组