32. 求众数的投票算法：用摩尔投票法找出数组中的众数

摩尔投票法（Boyer-Moore Voting Algorithm）是一种有效的算法，用于在数组中找出众数。众数是指在数组中出现次数超过一半的元素。摩尔投票法可以在线性时间 O(n) 和常数空间 O(1) 下完成这个任务。

1. 算法思路

摩尔投票法的核心思想是通过两次遍历来确定众数：

1. 第一遍遍历：假设第一个元素为候选人，然后遍历数组，当遇到相同的元素时，计数器加一；遇到不同的元素时，计数器减一。如果计数器为零，则将当前元素作为新的候选人。最后剩下的候选人就是可能的众数。
2. 第二遍遍历：验证第一遍得到的候选人是否确实是众数（即它的出现次数是否超过数组长度的一半）。

2. 代码实现

public class MajorityElement {

    // 第一阶段：找出可能的众数
    public int findCandidate(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 boolean isMajority(int[] nums, int candidate) {
        int count = 0;
        for (int num : nums) {
            if (num == candidate) {
                count++;
            }
        }
        return count > nums.length / 2;
    }

    // 主方法：使用摩尔投票法找出众数
    public int majorityElement(int[] nums) {
        int candidate = findCandidate(nums);
        if (isMajority(nums, candidate)) {
            return candidate;
        } else {
            throw new IllegalArgumentException("No majority element in the array");
        }
    }

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

3. 示例解释

假设输入数组为 [2, 2, 1, 1, 1, 2, 2]：

• 第一遍遍历：
  • 2 的计数器开始为 1。
  • 下一个 2，计数器变为 2。
  • 遇到 1，计数器减 1，变为 1。
  • 下一个 1，计数器再减 1，变为 0。
  • 因为计数器为 0，重新将 1 作为候选人，并将计数器置为 1。
  • 下一个 1，计数器加 1，变为 2。
  • 遇到 2，计数器减 1，变为 1。
  • 最后一个 2，计数器加 1，变为 2。
  • 结束时，候选人为 2。
• 第二遍遍历：
  • 验证 2 是否为众数，2 出现了 4 次，确实是众数（数组长度为 7，超过一半的元素数量为 3.5）。

最终确定 2 是众数。

4. 复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。我们遍历数组两次。
• 空间复杂度：O(1)，只用了常数空间来保存候选人和计数器。

5. 总结

摩尔投票法是一种高效且简洁的算法，用于找出数组中的众数。该算法利用了计数的方式来抵消非众数的影响，最终确定可能的众数。摩尔投票法在解决众数问题时具有优越的时间和空间效率。