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

题目主要信息:

• 题目给出一个长度为n的数组，其中有一个数字出现次数超过了数组长度的一半，需要我们找出这个数字
• 输入数组非空，保证有解，这样就不用考虑特殊情况

具体思路:

首先我们分析一下，数组某个元素出现次数超过了数组长度的一半，那它肯定出现最多，而且只要超过了一半，其他数字不可能超过一半了，必定是它。

如果给定的数组是有序的，那我们在连续的相同数字中找到出现次数最多即可，但是题目没有要求有序，一种方法是对数组排序后解决，但是时间复杂度就上去了。那我们可以考虑遍历一次数组统计各个元素出现的次数，找到出现次数大于数组长度一半的那个数字。

• step 1：用unordered_map构建一个哈希表，统计数组元素各自出现了多少次，即key值为数组元素，value值为其出现次数。
• step 2：遍历数组，每遇到一个元素就把哈希表中相应key值的value值加1，用来统计出现次数。
• step 3：本来可以统计完了之后统一遍历哈希表找到频次大于数组长度一半的key值，但是根据我们上面加粗的点，只要它出现超过了一半，不管后面还有没有，必定就是这个元素了，因此每次统计后，我们都可以检查value值是否大于数组长度的一半，如果大于则找到了。

具体过程可以参考下列图示：

代码实现:

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        unordered_map<int, int> mp; //无序哈希表统计每个数字出现的次数
        for(int i = 0; i < numbers.size(); i++){ //遍历数组
            mp[numbers[i]]++; //哈希表中相应数字个数加1
            if(mp[numbers[i]] > numbers.size() / 2) //一旦有个数大于长度一半的情况即可返回
                return numbers[i];
        }
        return 0;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历一次数组，哈希表每次操作的复杂度都是$O(1)O(1)$
• 空间复杂度：$O(n)O(n)$，最坏情况下$n\mathrm{/}2+1n/2+1$个相同的数字，其他都不同，则共有$n\mathrm{/}2n/2$个不同的数字，哈希表长度需要达$n\mathrm{/}2n/2$