如何理解摩尔投票法?


class Solution {
public:
  vector<int> majorityElement(vector<int> &nums) {
    auto n = nums.size();
    vector<int> ret;
    if (n == 0) {
      return ret;
    }
    auto n1 = nums[0], c1 = 0;
    auto n2 = nums [0], c2 = 0; // 注意两个都初始化为 nums [0]

    for (unsigned i = 0; i < n; ++i) { // 注意从 i = 0 开始
      auto num = nums[i];
      if (num == n1) {
        c1++;
        continue;
      }
      if (num == n2) {
        c2++;
        continue;
      }
      if (c1 == 0) {
        n1 = num;
        c1++;
        continue;
      }
      if (c2 == 0) {
        n2 = num;
        c2++;
        continue;
      }
      c1--;
      c2--;
    }

    // statistics
    c1 = 0;
    c2 = 0;

    // 会不会出现 n1 = n2?
    for (unsigned i = 0; i < n; ++i) {
      if (nums[i] == n1) {
        c1++;
      } else if (nums [i] == n2) { // 注意这里是 else if
        c2++;
      }
    }
    if (c1 > n / 3) {
      ret.push_back(n1);
    }
    if (c2 > n / 3) {
      ret.push_back(n2);
    }
    return ret;
  }
};