一个无序数组里面怎么查找出现次数大于数组长度一半的数

Question

方法一：排序

1. 对无序数组进行排序，假设数组长度为n，取排序后的第 n/2 个数，该数是出现次数大于数组长度一半的数。
2. 时间复杂度为O(nlogn)，因为排序的时间复杂度是 O(nlogn)。

方法二：摩尔投票法

1. 从第一个数开始，设当前数为候选数，出现次数为1。
2. 遍历数组，如果下一个数与候选数相同，出现次数+1，如果不同，出现次数-1。
3. 出现次数减为0时，更换候选数为当前数。
4. 最后剩下的候选数即为出现次数大于数组长度一半的数。
5. 时间复杂度为O(n)。

方法三：哈希表

1. 遍历数组，将每个数作为哈希表的键，出现次数作为哈希表的值。
2. 遍历哈希表，找出值大于n/2的键即可。
3. 时间复杂度为O(n)，但需要额外的哈希表空间。

以下是一种可能的解决方案：

1. 将数组元素放入哈希表中，并统计每个元素的出现次数。
2. 遍历哈希表，找到出现次数大于数组长度一半的元素。
3. 如果找到了这样的元素，则返回该元素。否则，返回 null。

代码如下：

public static Integer findMajorityElement(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    int n = nums.length;

    // 统计每个元素的出现次数
    for (int num : nums) {
        int count = map.getOrDefault(num, 0) + 1;
        map.put(num, count);
    }

    // 寻找出现次数大于数组长度一半的元素
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        if (entry.getValue() > n / 2) {
            return entry.getKey();
        }
    }

    // 没有找到该元素
    return null;
}

该算法的时间复杂度为 O(n)，空间复杂度为 O(n)。