LeetCode 剑指 Offer 39. 数组中出现次数超过一半的数字

约 5 分钟
文章信息 17 个分类 5 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 20-50 字节跳动 美团 阿里巴巴 腾讯 百度 滴滴 网易 小米 虾皮 剑指 Offer 剑指 Offer（第 2 版）
标签
数组 哈希表 排序 分治 计数
目录

题目描述

✅ 剑指 Offer 39. 数组中出现次数超过一半的数字

image-20241107211104539

题意分析

给定一个长度为 $n$ 的数组，其中存在某个数字出现次数严格超过 $\lfloor n/2 \rfloor$，要求把它找出来并返回。

「严格超过一半」这个约束比它看上去更强。它意味着：这个数字的出现次数，比数组里其他所有数字的出现次数加起来还要多；同时它也保证了这样的数字最多只有一个，不存在并列，因此答案唯一。题目还明确保证它一定存在，所以不需要考虑「找不到」的返回值。

元素的取值范围没有限制，可能是任意整数，包括负数和重复出现的极端值，因此不能假设可以拿值当下标去开计数数组。

边界情形包括：数组只有一个元素，答案就是它本身；数组元素全部相同；以及多数元素被打散在数组两端、中间夹着大量其他值的情形，比如 [2,2,1,1,1,2,2]。

解法：Boyer-Moore 投票

核心思路

哈希计数需要 $O(n)$ 空间，排序需要 $O(n\log n)$ 时间；题目“某个数严格超过一半”的条件允许使用 Boyer-Moore 投票做到一次扫描、常数空间。

把两个不同的数看成一对并同时抵消。多数元素的数量大于其他元素总数，所以无论按什么顺序抵消，它都不可能被全部消掉。代码用 candidate 表示当前未抵消元素的值，用 count 表示其净数量。

循环不变量是：处理完任意前缀后，删除若干对值不同的元素，剩余部分恰好是 count 个 candidate。count == 0 时前缀已完全抵消，可从当前元素重新选择候选。扫描结束后若最终候选不是多数元素，那么真正的多数元素只能全部位于已抵消的数对中，而每对最多包含一个多数元素，其数量不可能超过一半，产生矛盾。因此在题目保证多数元素存在时，最终候选就是答案。

解题步骤

  1. 初始化 count = 0，此时还没有有效候选。
  2. 遍历数组；若 count == 0，把当前数设为新候选。
  3. 当前数等于候选时 count++，否则 count--，表示抵消一对不同元素。
  4. 题目保证多数元素存在，遍历结束后直接返回候选；若没有这项保证，还必须二次计数验证。

[2,2,1,1,1,2,2] 中，候选/计数 依次为 2/1 → 2/2 → 2/1 → 2/0 → 1/1 → 1/0 → 2/1，最终得到 2。

代码实现

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
}

func majorityElement(nums []int) int {
    candidate := 0
    count := 0

    for _, num := range nums {
        if count == 0 {
            candidate = num
        }
        if num == candidate {
            count++
        } else {
            count--
        }
    }
    return candidate
}

复杂度分析

  • 时间复杂度：$O(n)$，数组只扫描一次；无多数元素保证时，验证候选再扫描一次，仍是 $O(n)$。
  • 空间复杂度：$O(1)$，只维护候选和计数。

关键点总结

  • 超过一半等价于“该元素数量大于其余所有元素之和”，这是配对抵消成立的前提。
  • count 是候选在抵消后的净票数，不是候选的真实出现次数。
  • 换候选后仍要处理当前这一票，所以“判零”和“加减票”是两个连续判断。
  • 是否需要二次验证取决于题目是否保证多数元素存在；这是面试中必须主动说明的前提。

易错点总结

  • 换候选后不加当前票：把两次判断写成 if/else，[1] 会留下 count = 0。
  • 初始化与起点不配套：若用 candidate = nums[0], count = 1，循环必须从下标 1 开始，否则首元素会被计算两次。
  • 把净票数当真实频次：候选可能多次更换，中途的 count 不能用于判断出现次数。
  • 忽略存在性前提：对 [1,2,3]，投票仍会给出候选，但它并未超过一半；这类变体必须二次验证。
  • 误以为多数元素必须连续：[2,1,2,1,2] 的多数元素分散出现，最长连续段等思路无效。

相似题目

题目 难度 考察点
169. 多数元素 简单 与本题完全同题，可直接复用同一份代码
229. 多数元素 II 中等 阈值变成 $n/3$，需维护两个候选并二次验证
面试题 17.10. 主要元素 简单 不保证多数元素存在，必须补一遍计数确认
LCR 004. 只出现一次的数字 II 中等 同样靠「抵消」思想，但抵消发生在二进制位计数上