31. 多数元素：找出数组中出现次数超过一半的元素

PangHu大约 3 分钟

寻找数组中出现次数超过一半的元素问题被称为“多数元素”问题。这是一个经典的问题，有多种解决方法，最有效的之一是使用摩尔投票算法。下面我将介绍几种常用的方法，并给出每种方法的 Java 实现。

一、哈希表法

1. 思路

利用哈希表存储每个元素出现的次数，然后遍历哈希表，找到出现次数超过一半的元素。

2. 代码实现

import java.util.HashMap;
import java.util.Map;

public class MajorityElementHashMap {

    public static int majorityElement(int[] nums) {
        Map<Integer, Integer> countMap = new HashMap<>();
        int majorityCount = nums.length / 2;

        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
            if (countMap.get(num) > majorityCount) {
                return num;
            }
        }

        // 题目保证了多数元素一定存在，所以这里不会运行到
        throw new IllegalArgumentException("No majority element found");
    }

    public static void main(String[] args) {
        int[] nums = {2, 2, 1, 1, 1, 2, 2};
        int result = majorityElement(nums);
        System.out.println("The majority element is: " + result);
    }
}

3. 时间复杂度和空间复杂度

时间复杂度：O(n)，遍历一次数组。
空间复杂度：O(n)，使用哈希表存储元素的出现次数。

二、排序法

1. 思路

如果数组排序，那么中间的那个元素一定是多数元素。原因是如果一个元素的出现次数超过一半，那么排序后该元素必定会占据数组的中间位置。

2. 代码实现

import java.util.Arrays;

public class MajorityElementSorting {

    public static int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    public static void main(String[] args) {
        int[] nums = {2, 2, 1, 1, 1, 2, 2};
        int result = majorityElement(nums);
        System.out.println("The majority element is: " + result);
    }
}

3. 时间复杂度和空间复杂度

时间复杂度：O(n log n)，排序数组的时间复杂度。
空间复杂度：O(1)，不需要额外的空间（或 O(n)，如果使用了排序算法的额外空间）。

三、摩尔投票法

1. 思路

摩尔投票算法是一种非常高效的算法，它基于以下两个假设：

假设数组中有一个元素是多数元素。
通过消除不同的元素对，最终剩下的元素就是多数元素。

具体步骤：

初始化一个候选者 candidate 和计数器 count。
遍历数组，如果当前元素等于 candidate，则 count++，否则 count--。
如果 count 变为 0，说明前面的部分不可能是多数元素，因此重新选择候选者。
遍历结束时，candidate 就是多数元素。

2. 代码实现

public class MajorityElementMooreVoting {

    public static int majorityElement(int[] nums) {
        int candidate = nums[0];
        int count = 1;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == candidate) {
                count++;
            } else {
                count--;
            }
            if (count == 0) {
                candidate = nums[i];
                count = 1;
            }
        }

        return candidate;
    }

    public static void main(String[] args) {
        int[] nums = {2, 2, 1, 1, 1, 2, 2};
        int result = majorityElement(nums);
        System.out.println("The majority element is: " + result);
    }
}

3. 时间复杂度和空间复杂度

时间复杂度：O(n)，只需遍历一次数组。
空间复杂度：O(1)，只使用了常数级别的额外空间。

四、总结

哈希表法：通过记录每个元素的出现次数来判断多数元素，适用于一般场景。
排序法：通过排序直接找到中间的元素来判断多数元素，适用于数据量不大且排序操作方便的场景。
摩尔投票法：最优解法，通过一遍扫描数组找到多数元素，空间复杂度最低，适用于大多数场景。

摩尔投票法是解决多数元素问题的最佳选择，因为它在时间复杂度和空间复杂度上都是最优的，尤其适合在不允许使用额外空间的情况下。