摩尔投票算法：查找多数元素

需要先区分两个概念：

• 多数元素：出现次数严格超过数组长度一半的元素。
• 众数：出现次数最多的元素，不要求超过一半。

摩尔投票算法可以在线性时间、常数空间内寻找多数元素，但不能直接解决没有“超过一半”保证的一般众数问题。

一、摩尔投票算法

算法维护一个候选值和一个计数器：

1. 如果计数器为 0，将当前元素设为候选值。
2. 当前元素等于候选值时，计数器加 1。
3. 当前元素不等于候选值时，计数器减 1。
4. 遍历完成后，候选值只是“可能的多数元素”，还需要再次验证。

不同元素可以两两抵消。如果某个元素出现次数超过其他所有元素出现次数之和，它不会在抵消过程中被完全消除，因此最终候选值一定是它。

二、C++ 实现

#include <optional>
#include <vector>

std::optional<int> MajorityElement(const std::vector<int>& nums) {
  if (nums.empty()) {
    return std::nullopt;
  }

  int candidate = 0;
  int balance = 0;

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

  int occurrences = 0;
  for (int value : nums) {
    if (value == candidate) {
      ++occurrences;
    }
  }

  if (occurrences > static_cast<int>(nums.size()) / 2) {
    return candidate;
  }
  return std::nullopt;
}

第一次遍历寻找候选值，第二次遍历验证候选值。时间复杂度为 O(n)，额外空间复杂度为 O(1)。

三、随机抽样方法

如果数组中确实存在多数元素，随机抽取一个下标，抽到多数元素的概率超过 1/2。对候选值进行完整计数并验证，重复抽样可以降低找不到多数元素的概率：

#include <optional>
#include <random>
#include <vector>

std::optional<int> RandomizedMajority(
    const std::vector<int>& nums,
    std::mt19937& generator,
    int attempts = 20) {
  if (nums.empty()) {
    return std::nullopt;
  }

  std::uniform_int_distribution<std::size_t> pick(
      0, nums.size() - 1);

  for (int attempt = 0; attempt < attempts; ++attempt) {
    const int candidate = nums[pick(generator)];
    int occurrences = 0;
    for (int value : nums) {
      if (value == candidate) {
        ++occurrences;
      }
    }

    if (occurrences > static_cast<int>(nums.size()) / 2) {
      return candidate;
    }
  }

  return std::nullopt;
}

这种方法每次尝试需要 O(n)，总复杂度为 O(attempts * n)。它可能因为多次抽不到多数元素而返回空结果，但不会把经过完整验证的非多数元素误判为多数元素。

在不需要随机化的情况下，摩尔投票算法更简单，并且可以确定性地在线性时间内完成任务。

四、一般众数问题

如果题目只保证“返回出现次数最多的元素”，而不保证该元素超过数组长度一半，就不能直接使用摩尔投票算法。此时可以使用哈希表统计频次，时间复杂度为 O(n)，空间复杂度为 O(n)。

五、总结

• 摩尔投票算法解决的是“出现次数超过一半”的多数元素问题。
• 候选值必须经过第二次遍历验证。
• 算法时间复杂度为 O(n)，额外空间复杂度为 O(1)。
• 一般众数问题需要统计频次，不能直接套用摩尔投票。