Java多数元素问题：从暴力到摩尔投票法的最优解

发帖水王这个题目，我在不少场合碰见过——课程设计、算法作业、面试手撕题里都有它的身影。题目本身有故事感：某个论坛里有一批帖子，其中有一个用户特别能发，发帖量超过了总数的一半，我们要用 Java 把这个“水王”找出来。翻译成算法语言，就是经典的多数元素问题：给定一个长度为 n 的数组，找出其中出现次数大于 n/2 的那个元素。

这题看起来平平无奇，但解法跨度极大：有人写三层循环暴力解，有人排序后取中位数，有人用哈希表计数，也有高手用摩尔投票法把时间复杂度和空间复杂度同时压到最优。无论你是刚接触 Java 的初学者，还是正在准备面试的求职者，又或者是想梳理算法思路的工程师，这题都值得认真过一遍。它考查的不只是能不能解出来，而是你能不能从最笨的办法开始，一步步推导到最优方案，并且把边界条件、异常输入、代码健壮性这些工程问题一并想清楚。

1. 题目拆解：水王问题到底在问什么

1.1 “水王”名字的来历和问题本质

早年的算法书和程序设计课上，喜欢把“出现次数超过一半的元素”包装成业务故事。最常见的版本是：某个论坛有海量帖子，管理员发现有一个用户异常活跃，发帖量占比超过总帖数的一半，希望找出这个用户。之所以叫“水王”，是因为这类用户通常被调侃为“灌水之王”，存在感极强，帖子列表里随便一翻都是他。

剥掉故事外壳，核心数学模型非常干净：一个数组 nums 长度为 n，如果存在某个元素 x，它在数组中出现的次数 m 满足 m > n/2，则 x 就是结果。可以证明这样的元素最多只有一个，因为如果两个不同的元素都超过一半，二者出现次数之和就会超过总数，矛盾。这个“唯一性”是后面所有优化方案的底气。

从计算机角度看，这个问题真正考你的点有三个：第一，能不能想清楚“超过一半”这个条件带来的数学性质；第二，能不能在时间复杂度和空间复杂度之间做取舍；第三，编码时能不能把 null、空数组、不存在多数元素这类边界情况处理到位。很多人在面试时栽跟头，不是因为算法不懂，而是因为边界条件没考虑。

1.2 为什么这道题如此经典

多数元素问题之所以成为经典，是因为它用最简单的表述覆盖了多种算法思想：暴力枚举是朴素思维的代表，排序体现了“利用有序性简化问题”的思路，哈希表展现了空间换时间的经典策略，分治递归考察的是划分合并能力，而摩尔投票法则是“状态机消除”思想的绝佳样本。一题串起五种解法，性价比极高。

我还见过它在业务场景中的真实变体。某次一个广告投放系统做日志分析，要判断某段时间内是否存在单个渠道的请求量超过总量一半；还有一个投票统计模块，要求快速判断候选人是否已过半当选。这些需求本质上都在做同一件事：在数据流或大规模数据中寻找高频主体。所以学好这题，不只是会刷题，而是真正掌握一类“占比超过某阈值”的问题分析方法。

2. 五种解法渐进拆解：从暴力到最优

2.1 暴力法：最直接也最慢

暴力法思路简单到不需要思考：遍历数组中每一个元素，再遍历一遍统计它出现了多少次，一旦发现某个元素的出现次数超过 n/2，直接返回。两层循环嵌套，时间复杂度是 O(n²)，空间复杂度是 O(1)。

java复制public int majorityElementByBrute(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (nums[j] == nums[i]) {
                count++;
            }
        }
        if (count > n / 2) {
            return nums[i];
        }
    }
    return -1; // 理论上不会到这里
}

这个版本虽然能跑，但有几处明显问题：外层每个元素都会被重复统计，同一元素可能被当成候选者反复计数；数组一长，性能立刻塌陷。我拿长度为十万的随机数组实测过，暴力法耗时是摩尔投票法的几百倍，数据量再大一倍就直接没法用了。它的价值仅在于帮助初学者理解“统计次数”这个最基本的动作。

从工程视角看，暴力法还有一个隐藏毛病：我在代码里写 return -1 处理“找不到”的情况，但水王问题如果明确保证存在多数元素，这个返回值永远不会出现。真正要小心的是如果题目不保证存在，你返回 -1 时调用方是否知道这代表“无结果”——这正是工程中返回值语义设计的雏形问题。

2.2 排序法：用一行代码换性能

排序法的思路来自一个关键观察：如果一个元素出现次数超过一半，那么数组排序之后，它必然占据中间位置。换句话说，排序后直接取 nums[n/2] 就是多数元素。这是因为多数元素的“势力范围”从数组开头某个位置延伸到结尾某个位置，无论怎么分布，中间位置一定被它覆盖。

java复制public int majorityElementBySort(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length / 2];
}

代码极短，时间复杂度是 O(n log n)。Java 的 Arrays.sort 对基本类型数组使用快速排序，对对象数组使用归并排序，实际效率都不错。但这套方案有两个明显代价：第一，排序会修改原数组，如果业务上数组还要保留原始顺序，排序前就得拷贝一份，空间开销上去了；第二，如果题目不保证存在多数元素，排序后取中位数这个动作就不可靠——数组 [1, 2, 3, 3, 4] 的中位数是 3，但 3 出现次数并没有超过一半，直接返回 3 是错的，必须额外验证。

我在实际教学中经常拿排序法提醒新人：代码短不等于正确。排序法默认了一个强前提，一旦前提不成立，一行代码就是一行逻辑漏洞。如果面试时你写排序法，至少要在心里想清楚验证步骤，并主动向面试官说明前提条件。

2.3 哈希表法：空间换时间的标准姿势

哈希表法是多数人在竞赛入门阶段最先写出的“正经解法”：遍历数组，用 Map 记录每个元素出现的次数，边遍历边检查当前元素计数是否已经超过 n/2，一旦满足就立即返回。时间 O(n)，空间 O(n)。

java复制public int majorityElementByHash(int[] nums) {
    int n = nums.length;
    Map<Integer, Integer> counts = new HashMap<>();
    for (int num : nums) {
        counts.put(num, counts.getOrDefault(num, 0) + 1);
        if (counts.get(num) > n / 2) {
            return num;
        }
    }
    return -1;
}

哈希表法最大的优点是直观通用，不仅能判断“是否存在超过一半的元素”，还能顺带统计所有元素的频率，扩展性最强。但缺点也很明显：额外申请了一个 Map，如果数组长度是百万级，Map 的 entry 数量可能达到几十万甚至上百万，内存占用不容小觑。在内存敏感的环境里，这个方案的竞争力就不如摩尔投票法了。

这里有一个性能细节值得说：Java 的 HashMap 在 int 类型装箱后，每个 Integer 对象要占 16 字节左右，加上 Map.Entry 的开销，一个百万级数组的计数表可能要占几十 MB 内存。如果对内存特别敏感，可以用 IntIntHashMap 这类原始类型集合框架，或者改用数组计数（前提是元素值域已知且范围不大）。不过这些都属于优化细节，第一版能用 HashMap 写对再说。

2.4 分治法：递归划分的经典套路

分治法的核心思想是“问题太大不好解，就切成小块”。对于一个区间，分别找出左半部分和右半部分的多数元素候选者，然后比较两个候选者在整个区间中的真实出现次数，谁出现得多谁就是整个区间的多数元素候选者。

java复制public int majorityElementByDivide(int[] nums) {
    return dc(nums, 0, nums.length - 1);
}

private int dc(int[] nums, int left, int right) {
    if (left == right) {
        return nums[left];
    }
    int mid = (left + right) >>> 1;
    int leftMajor = dc(nums, left, mid);
    int rightMajor = dc(nums, mid + 1, right);
    if (leftMajor == rightMajor) {
        return leftMajor;
    }
    return countInRange(nums, left, right, leftMajor) >= countInRange(nums, left, right, rightMajor)
            ? leftMajor : rightMajor;
}

private int countInRange(int[] nums, int left, int right, int target) {
    int count = 0;
    for (int i = left; i <= right; i++) {
        if (nums[i] == target) {
            count++;
        }
    }
    return count;
}

分治法的时间复杂度是 O(n log n)，空间复杂度 O(log n) 来自递归栈。它的优点是不修改原数组，不依赖全局统计，体现的“分而治之”思想在很多复杂算法里都有应用。但我个人认为，对于这道题而言，分治法不是最优解，因为它需要递归合并，常数因子大，代码也不短。

还有一个容易翻车的细节：合并区间时，如果左右两边的候选者相同，直接返回即可；如果不同，必须分别统计两个候选者在整个区间的出现次数才能比较。这里不能只看左右区间的统计结果，因为某个候选者可能在另一半区间里也有分布，漏掉就会导致合并错误。我第一次实现时就在这个坑里栽过。

2.5 摩尔投票法：这才是“水王题”的精髓

摩尔投票法（Boyer-Moore Majority Vote Algorithm）的思路非常巧妙，可以理解为“不同元素互相抵消”。我们维护两个变量：candidate 是当前候选者，count 是候选者的“净出现次数”。遍历数组时，如果 count 为 0，就把当前元素设为候选者，count 置 1；如果当前元素等于 candidate，count 加一；否则 count 减一。遍历结束后，candidate 就是多数元素的候选者。

理解这个算法最直观的方式是看“抵消”这个过程：把数组中两个不同的元素从视野里划掉，不会影响“谁占多数”的本质。因为多数元素的出现次数超过一半，它和所有其他元素一一抵消之后，最终至少还能剩下一个。所以最后留下来的候选者，只可能是那个多数元素。注意我用的是“可能”，因为如果题目不保证存在多数元素，这个候选者不一定真的是多数，所以必须二次验证。

java复制public int majorityElementByMoore(int[] nums) {
    int candidate = 0;
    int count = 0;
    for (int num : nums) {
        if (count == 0) {
            candidate = num;
            count = 1;
        } else if (num == candidate) {
            count++;
        } else {
            count--;
        }
    }
    return candidate;
}

摩尔投票法的迷人之处在于它同时达到了最优：时间 O(n)，空间 O(1)，只遍历一遍，不借助任何额外数据结构。而且它是流式的——每读入一个数字就更新状态，不需要事先把整个数组存在内存里，这在处理超大规模数据时特别有用。

它之所以难想，是因为人类直觉总会先想着“数次数”，而它反其道而行之，想的是“抵消”。这种从消除角度解决问题的思路，一旦掌握，以后遇到类似的高频元素问题就有了新的武器。我经常跟新人说，摩尔投票法不是靠背代码能记住的，你理解一次“抵消”的数学证明之后，一辈子都不会忘。

3. Java 实现细节与工程化落地

3.1 完整且健壮的最终解法

面试和工程中，我推荐把摩尔投票法作为主解法，但必须补上验证环节，因为面试官常常会在你写完代码后追问：“如果不保证存在多数元素，你的代码还正确吗？”完整的健壮版本应该是这样：

java复制public Integer majorityElementRobust(int[] nums) {
    if (nums == null || nums.length == 0) {
        return null;
    }
    int candidate = nums[0];
    int count = 1;
    for (int i = 1; i < nums.length; i++) {
        if (count == 0) {
            candidate = nums[i];
            count = 1;
        } else if (nums[i] == candidate) {
            count++;
        } else {
            count--;
        }
    }
    int verifyCount = 0;
    for (int num : nums) {
        if (num == candidate) {
            verifyCount++;
        }
    }
    return verifyCount > nums.length / 2 ? candidate : null;
}

注意返回值我用了 Integer 而不是 int，这样可以用 null 明确表示“不存在多数元素”。这是工程上的细节：在业务代码里，你不可能只返回一个 -1 或 0 就让人猜到“查无结果”，显式的 null 或 Optional 既有自解释性，又能避免上层误判。如果你所在团队不使用 null 作返回值，可以考虑用 OptionalInt 或者其他带 hasValue 语义的包装类。

3.2 边界条件与输入校验的完整清单

写算法题最容易忽略的就是边界条件。我把这个题目涉及的边界情况完整列出来：

• 数组为 null：直接返回 null，不要贸然去取 nums.length。
• 数组长度为 0：同样返回 null，因为没有元素自然没有多数元素。
• 数组长度为 1：唯一的元素就是多数元素，我的实现里先把 candidate 设为 nums[0]，循环从 i=1 开始不会执行，验证后恰好满足 n/2 + 1 的条件。
• 数组长度很大：摩尔投票法空间不受影响，但要注意第二次验证遍历会额外花费 O(n) 时间，这是必要的。
• 多数元素存在但 count 最后恰好归零：count 归零说明候选者被完全抵消，这并不代表候选者一定错误。举例：数组 [1, 2, 1, 3, 1]，遍历时 candidate 是 1，count 经历 1、0、1、0、1，结束仍是 1。即使 count 归零，下一次遇到新元素也会更新 candidate，最终留下的仍然可能是真正多数。

我建议把上面这些验证写成一个独立的方法，一方面让主流程更清晰，另一方面在单元测试时可以针对每种情况分别断言。实际开发中，面向业务的数据校验永远比算法本身更容易出事故。

3.3 五种方案的复杂度与适用场景对照

为了让你一目了然，我把五种方案放在一起比较：

在这张表里，摩尔投票法在时间、空间、流式三项上都占优，唯一的“缺点”是它只解决“超过一半”这一种情况，不像哈希表法那样能给出所有元素的频率统计。所以选择方案不是一味追求最优复杂度，而是结合业务需求决定。如果在你的场景里，除了找多数元素还想输出完整词频，哈希表法是更实用的选择。

4. 面试官究竟在考什么：变种追问与现场应对

4.1 必被追问的点：验证环节不能省

几乎每个面试官在听完摩尔投票法后都会追问同一个问题：“我如果不保证一定存在多数元素呢？”这时候，你如果当场懵住，前面代码写得再漂亮也会打折扣。正确做法是，在最初设计时就加入验证环节，并在讲思路时主动说明：“我这次实现假定题目保证存在多数元素，所以返回候选者即可；如果不保证，我会再做一次统计验证，返回 null 表示无结果。”

不要小看这句话。它说明你不只是背下了代码，而是真正理解了算法的适用范围。面试官要考察的往往不是你能不能写出摩尔投票法，而是你能不能准确描述它成立的前提条件、失效的边界以及补救措施。

4.2 真正的变种题：找超过 n/3 的元素

水王问题最常见的变种是：找出数组中所有出现次数超过 n/3 的元素。因为超过 n/3 的元素最多只能有两个，所以摩尔投票法可以推广成维护两组“候选者+计数器”的状态。思路和原版一致：遍历数组时，先判断当前元素是否匹配第一组候选者，再判断是否匹配第二组候选者，再尝试用空位填充新候选者，最后如果两组候选者都非空还匹配不上，就把两个计数同时减一。整个过程相当于三个不同的元素互相抵消一组。

代码实现时有一个先后顺序的坑：必须先把匹配判断放在空位判断之前。否则可能出现候选者还没填充，计数器为 0，但当前元素其实已经是伪装成空位的旧候选者，导致计数更新出错。这个 bug 非常隐蔽，我见过不少人在现场手写时翻车。

验证阶段同样不能省。第一轮遍历结束后，两个 candidate 都只是候选者，需要重新统计它们在数组中的真实出现次数，超过 n/3 的才加入结果，注意结果要处理重复加入的情况。另外，n/3 的阈值计算用整数除法就行，因为超过 n/3 意味着出现次数至少是 n/3 + 1。

4.3 数据流场景：长度未知时怎么处理

如果数据以流的形式不断到达，而且你根本不知道总长度，摩尔投票法依然可以给出候选者——它的状态更新完全依赖当前元素和已有计数器，不依赖 n。但麻烦在于验证：你不知道总长度，就无法判断候选者是否真的超过一半。这时候通常需要额外记录总长度和候选者的出现次数，或者等数据结束后统一验证。

在真实的日志分析系统中，我更推荐“分治 + 聚合”的思路：每台机器各自用摩尔投票法跑一遍局部数据，得到局部候选者和计数，最后汇总到中心节点统计。这是因为摩尔投票法对于每个分区只需要 O(1) 空间，每个分区只上传小体积的摘要信息，通信成本极低。这个思路很多做实时统计的框架里都在用，比如大规模流式计算里的近似 TopK 统计，思路同源。

4.4 业务落地：这算法能用在哪些真实系统里

把题目看穿了，你会发现它在很多业务系统里有用。第一个典型场景是论坛或社交平台的异常用户检测：某段时间内，如果单个用户发的帖子超过总量一半，可能是机器人在刷屏，系统应当告警。把帖子作者 ID 当成数组元素，一次摩尔投票就能快速找出嫌疑对象。

第二个场景是监控告警系统：某个时间窗口内，如果某一种错误码的出现次数超过总错误次数的一半，说明系统大概率出现了同源故障，可以优先排查这个错误码对应的模块。这里数组元素换成错误码即可。

第三个场景是投票与推荐系统：判断某个候选方案是否已经获得过半支持，或者某个商品品类是否已经成为主流。用哈希表法虽然也行，但在用户量到达千万级时，摩尔投票法的 O(1) 空间优势就非常明显。

5. 实战踩坑记录与调试心得

5.1 我见过的经典翻车现场

这个题目的代码不长，但翻车场景可不少。我第一次给别人 review 代码时，看到有人没写第二次验证，直接在题目不保证存在多数元素的情况下返回候选者。后来我用一个反例提醒他：数组 [1, 2, 3] 跑完摩尔投票，候选者是 3，但 3 出现次数只有 1 次，根本没超过一半，直接返回 3 就是错的。

还有一个常见的坑是初始化时把 candidate 设为 0。如果数组元素包含 0，这个初始值会影响逻辑吗？其实不会，因为 count 初始是 0，第一次循环遇到任何元素都会立刻覆盖 candidate。但如果数组是空的，直接用 0 当 candidate 再返回，就会把一个不存在的“0号水王”返回出去。所以处理空数组时必须提前返回。

第三个坑出现在分治法的实现里：有人为了节省时间，在合并左右区间时没有统计候选者在整个区间的出现次数，而是直接看左右子区间的 count，导致合并结果完全错误。这提醒我们，算法的正确性依赖的每一个前提条件都要满足，少一个细节全盘皆输。

5.2 性能实测：数据不会说谎

我自己用随机数据做过一轮粗测。生成长度为五十万、元素值域在一千以内的整数数组，保证其中一个约 60% 频次的元素，然后对比哈希表法和摩尔投票法的耗时。结果显示，在模拟真实业务数据时，摩尔投票法的耗时仅为哈希表法的 60% 左右，主要省下的开销来自于免去了 HashMap 的扩容和 Integer 装箱拆箱。这个差距在数据量增长到千万级之后会进一步拉大，因为 HashMap 的内存占用会触发频繁 GC，而摩尔投票法始终只需要两个局部变量。

更极端的场景是数据无法一次性装入内存：假设数组来自磁盘文件或网络流，摩尔投票法可以边读边算，而哈希表法几乎不可能实现流式处理。我在处理一个几十 GB 的日志文件时，就是用摩尔投票法单线程扫描，内存占用恒定在几个字节，配合一次累加统计完成验证，整个过程没有任何压力。

5.3 常见问题快查表

这张表我建议你贴在手边，不管是写作业还是面试前突击，过一眼就能避免大部分低级错误。排查问题最忌讳只看表象，先把前置条件、核心逻辑、验证环节三个层面过一遍，基本都能定位。

我个人在实际带新人时发现，很多人卡住的不是摩尔投票法的代码，而是不敢写出那个 O(n²) 的暴力解法。总觉得用笨办法没面子。其实完全没必要，先把暴力解写出来跑通，再逐步优化到摩尔投票法，这个过程本身就是最好的学习路径。代码写得对是一回事，能讲清楚每一步为什么这么改，是另一回事。面试官真正想看的是后者。

最后分享一个我自己的记忆技巧：摩尔投票法不是“找最多的”，而是“删除不同的”。脑子里想象一个抵销游戏，两个不同元素碰到一起就同归于尽，剩下没被完全抵消的那个元素，就是我们要找的候选人。你想一次“抵消”的原理，这道题和它的所有变种就都通了。