169. 多数元素

169. 多数元素 - 力扣（LeetCode）

class Solution {
public:
  int majorityElement(vector<int>& nums) {
    std::unordered_map<int, int> Map;
    for (int X : nums)
      if (++Map[X] > nums.size() / 2)
        return X;
    std::unreachable();
  }
};

既然保证众数有大于 $\left\lfloor\dfrac n2\right\rfloor$ 的基数，我们就直接用哈希表，可以得到一个 $\mathrm O(n)$ 的时空复杂度。

不过官方题解里给的随机化算法有点吓人，直接级数求期望了，然而还确实是对的：

$$ \begin{aligned} E\left(I_{\mathrm{prob}}\right)&\le E(I_{1/2})\\ &=\lim_{n\to\infty}\sum_{i=1}^n i\cdot\frac1{2^i}&\left[E(X)=\sum _ix_ip_i\right]\\ &=2 \end{aligned} $$

统计学这一块。

这个投票算法也挺好的，很符合直觉，而且我确实也想过这样做的可能性——不过没有意识到「候选」（Candidate）和「净和」（Net）在解题当中的重要性，所以当时并没有想到具体该怎么做。

class Solution {
public:
  int majorityElement(vector<int>& nums) {
    int Candidate{};
    int Net{};
    for (int X : nums) {
      if (Net == 0) {
        Candidate = X;
        ++Net;
      } else {
        if (Candidate != X)
          --Net;
        else
          ++Net;
      }
    }
    return Candidate;
  }
};

二刷

class Solution {
public:
  int majorityElement(vector<int>& nums) {
    while (true) {
      int Count = 0;
      // Select a candidate randomly.
      int Candidate = nums[rand() % nums.size()];
      // Scan the array for its count.
      for (int N : nums) {
        if (N == Candidate)
          ++Count;
      }
      // Determine whether it's the mode.
      if (Count > nums.size() / 2)
        return Candidate;
    }
    unreachable();
  }
};

这个随机化真的有点吓人。随机选数——统计个数——验证，这怎么看都至少是 $\mathrm O\left(n^2\right)$ 的感觉，结果是 $\mathrm O(n)$，我真的。

三刷

class Solution {
public:
  int majorityElement(vector<int>& nums) {
    int Net = 1, Elem = nums.front();
    for (int i = 1; i < nums.size(); ++i) {
      if (nums[i] == Elem) {
        ++Net;
      } else {
        --Net;
        if (Net == 0) {
          // Reset the vote.
          Elem = nums[i];
          Net = 1;
        }
      }
    }
    return Elem;
  }
};

还是这个投票法比较看起来没那么吓人一点。

注意我这里跟二刷的区别是Net的初值设置为1了。这也是可以的，而且似乎更干净一些，就是for循环也需要从1开始。