Leetcode 229 Majority Element II

这是一道摩尔投票的题目。 相关题目169.Majority Element

题目要求:数组的长度是 $n$,要选出出现次数大于 $\frac{n}{3}$ 的元素。

很明显,一个长度为 $n$ 的数组,其中出现次数大于 $\frac{n}{3}$ 的元素,最多有2个。那么继续使用摩尔投票的思路,不过记录元素个数的变量有2个($ca, cb$),看看出现次数最多的2个元素 ($a, b$) 各出现多少次,如果满足条件,就添加到结果数组里。

static int x = [] () {ios::sync_with_stdio(false); cin.tie(0); return 0;} ();
class Solution {
 public:
  vector<int> majorityElement(vector<int>& nums) {
    int a = 0, b = 0, ca = 0, cb = 0;
    for (const int num: nums) {
      if (num == a) {
        ++ca;
      } else if (num == b) {
        ++cb;
      } else if (ca == 0) {
        a = num;
        ca = 1;
      } else if (cb == 0) {
        b = num;
        cb = 1;
      } else {
        --ca; --cb;
      }
    }

    ca = 0; cb = 0;
    for (const int num: nums) {
      if (num == a) ++ca;
      else if (num == b) ++cb;
    }
    const int c = nums.size() / 3;
    vector<int> res;
    if (c < ca) res.push_back(a);
    if (c < cb) res.push_back(b);
    return res;
  }
};

#直达链接

LeetCode 229. Majority Element II