链接：https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163 来源：牛客网

1.题干描述

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

数据范围：n \le 50000n≤50000，数组中元素的值 0 \le val \le 100000≤val≤10000 要求：空间复杂度：O(1)O(1)，时间复杂度 O(n)O(n)

输入描述: 保证数组输入非空，且保证有解

示例1

输入 [1,2,3,2,2,2,5,4,2]
输出2

示例2

输入 [3,3,3,3,2,2,2]
输出3

示例3

输入 [1]
输出1

2.题目分析

我们可以将数组进行排序，如果中间数字的个数大于数组一半长度，则该数组一定是要找的数字，其他数字的个数一定小于数组长度（因为找的是中间数字）。

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

3.我的总结

除了上述方法，我们还可以引入一种查找众数的方法： 首先需要已知数组中存在众数，遍历整个数组，将不同的数字进行两两消去，剩下的数一定是众数。