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

题目主要信息:

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

举一反三：

学习完本题的思路你可以解决如下题目：

BM52. 数组中只出现一次的两个数字

BM53. 缺失的第一个正整数

方法：哈希表（推荐使用）

知识点：哈希表

哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在$O(1)O(1)$时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

思路：

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

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

具体做法：

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

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        //哈希表统计每个数字出现的次数
        HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); 
        //遍历数组
        for(int i = 0; i < array.length; i++){ 
            //统计频率
            if(!mp.containsKey(array[i]))
                mp.put(array[i], 1);
            else
                mp.put(array[i], mp.get(array[i]) + 1);
            //一旦有个数大于长度一半的情况即可返回
            if(mp.get(array[i]) > array.length / 2) 
                return array[i];
        }
        return 0;
    }
}

C++实现代码：

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

Python实现代码：

class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        #无序哈希表统计每个数字出现的次数
        mp = dict() 
        #遍历数组
        for i in range(len(numbers)): 
            if numbers[i] in mp:
                #哈希表中相应数字个数加1
                mp[numbers[i]] += 1  
            else:
                mp[numbers[i]] = 1
            #一旦有个数大于长度一半的情况即可返回
            if mp[numbers[i]] > (int)(len(numbers) / 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$