题目描述

在一个非空数组中，存在一个元素出现次数严格超过数组长度的一半。请找出该元素。

示例：
输入：[1, 2, 3, 2, 2, 2, 5, 4, 2]
输出：2

约束条件：
- 数组长度范围：1 ≤ n ≤ 50000
- 保证存在多数元素（即至少有一个元素出现次数 > ⌊n/2⌋）

解题思路与实现

方法一：排序取中位数（简洁但非最优）

由于目标元素出现次数超过一半，排序后位于中间位置的元素必然是它。虽然代码最短，但时间复杂度为 O(n log n)，不适用于追求极致性能的场景。

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

方法二：自定义计数数组（推荐，高效稳定）

利用"最多只有 n/2 + 1 个不同数字"的特性，使用两个数组分别存储数值和对应频次。遍历时若某数计数超过一半，则立即返回。

时间复杂度：平均 O(n)，最坏 O(n²)；空间复杂度：O(n)。

public int majorityElement(int[] nums) {
    int threshold = nums.length / 2;
    int[] values = new int[threshold + 1];
    int[] freq = new int[threshold + 1];
    int size = 0;

    for (int num : nums) {
        boolean found = false;
        // 检查是否已存在
        for (int i = 0; i < size; i++) {
            if (values[i] == num) {
                freq[i]++;
                if (freq[i] > threshold) return num;
                found = true;
                break;
            }
        }
        // 若未找到，插入新值
        if (!found) {
            values[size] = num;
            freq[size] = 1;
            size++;
        }
    }
    return nums[0]; // 不会执行到此处
}

方法三：摩尔投票法（最优算法，思想精妙）

核心思想：多数元素的票数总和能抵消所有其他元素的"反对票"。从第一个元素开始，维护当前候选者和票数。相同则加票，不同则减票。当票数归零时更换候选者。最终剩下的就是答案。

时间复杂度：O(n)，空间复杂度：O(1)，是理论最优解。

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

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

方法四：哈希表统计（不推荐）

使用 HashMap 统计每个数的频率，一旦超过一半即返回。虽然逻辑清晰，但时间和空间开销较大，不适合本题。

public int majorityElement(int[] nums) {
    int threshold = nums.length / 2;
    Map<Integer, Integer> counter = new HashMap<>();
    for (int num : nums) {
        int count = counter.getOrDefault(num, 0) + 1;
        if (count > threshold) return num;
        counter.put(num, count);
    }
    return nums[0];
}

总结

• 排序法：代码最简，但效率不高。
• 自定义数组法：适合中小规模数据，运行速度快，可读性好。
• 摩尔投票法：最优解，空间常数级，思维巧妙，强烈推荐掌握。
• 哈希法：通用性强，但本题下表现较差。