题解 | #数组中出现次数超过一半的数字#

题意思路：
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。你可以假设数组是非空的，并且给定的数组总是存在多数元素。1<=数组长度<=50000

方法一:排序寻找中位值
题目保证给定数组总是存在多数元素，所有可以将数组排序后，此时数组中出现次数超过一半的数字一定是已排序数组的中位数。

图解：

复杂度分析

时间复杂度：O(NlogN)，N数组的长度，遍历数组，排序NlogN；

空间复杂度：O(1)，未开辟新空间。

代码：

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        sort(numbers.begin(), numbers.end());//先排序使数组有序
        int number=numbers[numbers.size()>>1];//此时数组中出现次数超过一半的数字一定是已排序数组的中位数。
        return number;
    }
};

方法二：哈希map

通过遍历数组元素，并统计每个数字出现的次数，找到出现次数超过一半的数字即可

复杂度分析

时间复杂度：O(NlogN)，N数组的长度，遍历数组，map的插入效率是O(logn)，读取效率是O(1)

空间复杂度：O(N)，数组存储与读取数据。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        map<int,int>mp;
        for(int i:numbers)mp[i]++;//遍历数组元素，并统计每个数字出现的次数
        for(int i:numbers){
            if(mp[i]>numbers.size()>>1)return i;//找到出现次数超过一半的数字
        }
        return 0;
    }
};