每日算法 — 使用java实现摩尔投票：Boyer-Moore线性时间找多数元素

算法引入

在数据处理和统计分析中，一个经典的问题是：如何在数组中高效找到出现次数超过一半的元素？ 这个元素被称为”多数元素”（Majority Element）。暴力解法需要 $O(n^2)$ 的时间复杂度，而基于哈希表的解法虽然能做到 $O(n)$ 时间，但需要 $O(n)$ 的额外空间。摩尔投票算法（Boyer-Moore Voting Algorithm）以惊人的简洁性，在 $O(n)$ 时间和 $O(1)$ 空间内解决了这个问题。

核心思想

摩尔投票算法的核心思想来源于”抵消”——如果数组中存在一个出现次数超过一半的元素，那么让这个元素与其他所有不同元素两两抵消，最终它仍然会留下。算法维护一个候选元素 candidate 和一个计数器 count：

• 遍历数组时，若 count 为 0，则将当前元素设为新的 candidate
• 若当前元素等于 candidate，则 count 加 1
• 否则 count 减 1（相当于一次”抵消”）

由于多数元素出现次数严格大于一半，即使它与所有其他元素都进行抵消，最终也至少会剩下一次。

完整Java实现

import java.util.Arrays;

/**
 * 摩尔投票算法实现
 * Boyer-Moore Voting Algorithm
 * 用于在O(n)时间、O(1)空间内找出数组中的多数元素
 */
public class BoyerMooreVoting {

    /**
     * 基础版：找出数组中出现次数超过n/2的多数元素
     * 前提是数组中一定存在多数元素
     *
     * @param nums 输入数组
     * @return 多数元素
     */
    public int majorityElement(int[] nums) {
        int candidate = nums[0];
        int count = 0;

        for (int num : nums) {
            // 计数器归零时，更换候选元素
            if (count == 0) {
                candidate = num;
            }
            // 当前元素与候选相同则加1，不同则减1（抵消）
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }

    /**
     * 增强版：先投票找出候选，再验证是否真的超过n/2
     * 适用于不确定是否存在多数元素的场景
     *
     * @param nums 输入数组
     * @return 多数元素，如果不存在则返回Integer.MIN_VALUE
     */
    public int majorityElementWithValidation(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Integer.MIN_VALUE;
        }

        // 第一阶段：投票找候选
        int candidate = nums[0];
        int count = 0;

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

        // 第二阶段：验证候选是否真的是多数元素
        int occurrence = 0;
        for (int num : nums) {
            if (num == candidate) {
                occurrence++;
            }
        }

        return (occurrence > nums.length / 2) ? candidate : Integer.MIN_VALUE;
    }

    /**
     * 扩展版：找出所有出现次数超过n/k的元素（k为任意阈值）
     * 利用摩尔投票的推广思想，同时维护(k-1)个候选
     *
     * @param nums 输入数组
     * @param k 阈值，找出现次数超过n/k的元素
     * @return 所有符合条件的元素数组
     */
    public int[] majorityElementGeneralized(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 1) {
            return new int[0];
        }

        // 同时维护(k-1)个候选及其计数器
        int[] candidates = new int[k - 1];
        int[] counts = new int[k - 1];

        // 第一阶段：投票
        for (int num : nums) {
            boolean found = false;
            // 若当前元素是某个候选，对应计数器加1
            for (int i = 0; i < k - 1; i++) {
                if (counts[i] > 0 && candidates[i] == num) {
                    counts[i]++;
                    found = true;
                    break;
                }
            }
            if (found) continue;

            // 若有计数器为0，设为新的候选
            for (int i = 0; i < k - 1; i++) {
                if (counts[i] == 0) {
                    candidates[i] = num;
                    counts[i] = 1;
                    found = true;
                    break;
                }
            }
            if (found) continue;

            // 否则所有候选的计数器都减1（抵消）
            for (int i = 0; i < k - 1; i++) {
                counts[i]--;
            }
        }

        // 第二阶段：验证各候选的真实出现次数
        java.util.List<Integer> result = new java.util.ArrayList<>();
        for (int i = 0; i < k - 1; i++) {
            if (counts[i] <= 0) continue;

            int candidate = candidates[i];
            int occurrence = 0;
            for (int num : nums) {
                if (num == candidate) {
                    occurrence++;
                }
            }
            if (occurrence > nums.length / k) {
                result.add(candidate);
            }
        }

        return result.stream().mapToInt(Integer::intValue).toArray();
    }

    /**
     * 主方法：测试所有版本的摩尔投票算法
     */
    public static void main(String[] args) {
        BoyerMooreVoting solution = new BoyerMooreVoting();

        // 测试基础版
        int[] nums1 = {2, 2, 1, 1, 1, 2, 2};
        System.out.println("数组: " + Arrays.toString(nums1));
        System.out.println("多数元素(>n/2): " + solution.majorityElement(nums1));

        // 测试验证版
        int[] nums2 = {3, 3, 4, 2, 4, 4, 2, 4, 4};
        System.out.println("\n数组: " + Arrays.toString(nums2));
        int result = solution.majorityElementWithValidation(nums2);
        System.out.println("多数元素(带验证): " + (result == Integer.MIN_VALUE ? "不存在" : result));

        // 测试不存在多数元素的情况
        int[] nums3 = {1, 2, 3, 4};
        System.out.println("\n数组: " + Arrays.toString(nums3));
        result = solution.majorityElementWithValidation(nums3);
        System.out.println("多数元素(带验证): " + (result == Integer.MIN_VALUE ? "不存在" : result));

        // 测试扩展版：找出现次数超过n/3的元素
        int[] nums4 = {1, 1, 1, 3, 3, 2, 2, 2};
        System.out.println("\n数组: " + Arrays.toString(nums4));
        int[] results = solution.majorityElementGeneralized(nums4, 3);
        System.out.println("出现次数>n/3的元素: " + Arrays.toString(results));
    }
}

算法正确性证明

为什么摩尔投票算法一定正确？假设数组长度为 $n$，多数元素 $m$ 出现次数为 $t > n/2$。

将数组中的元素分为两类：等于 $m$ 的和不等于 $m$ 的。在遍历过程中，只有当当前元素不等于 candidate 时，count 才会减少。最坏情况下，每次 $m$ 出现时 candidate 都不是 $m$，此时 $m$ 会先被设为 candidate，然后后续的非 $m$ 元素会将其抵消。但由于 $t > n/2$，即使所有非 $m$ 元素都与 $m$ 配对抵消，$m$ 仍然会剩余至少 $2t – n > 0$ 次，因此最终 candidate 一定是 $m$。

复杂度分析

应用场景

摩尔投票算法在以下场景有广泛应用：

• 分布式系统一致性：在多个节点投票选举 leader 时快速确定多数派
• 数据流处理：在流式数据中实时检测高频元素，空间受限时尤为有效
• DNA序列分析：寻找基因组中出现频率最高的碱基序列
• 投票系统：电子投票中快速验证获胜者是否获得过半选票

摩尔投票算法的优雅之处在于，它将一个看似需要复杂数据结构的问题，用极其简洁的”抵消”思想完美解决，是算法设计中”以简驭繁”的典范。