229. 求众数II

给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

解法：Boyer-Moore投票法

相似题目：169. 多数元素

class Solution {
 public:
  vector<int> majorityElement(vector<int>& nums) {
    vector<int> result;
    if (nums.empty()) return result;
    int candidate1 = nums[0], count1 = 0;
    int candidate2 = nums[0], count2 = 0;

    for (int num : nums) {
      if (candidate1 == num) {
        count1++;
      } else if (candidate2 == num) {
        count2++;
      } else if (count1 == 0) {
        candidate1 = num;
        count1++;
      } else if (count2 == 0) {
        candidate2 = num;
        count2++;
      } else {
        count1--;
        count2--;
      }
    }

    count1 = 0;
    count2 = 0;
    for (int num : nums) {
      if (candidate1 == num)
        count1++;
      else if (candidate2 == num)
        count2++;
    }

    if (count1 > nums.size() / 3) result.push_back(candidate1);
    if (count2 > nums.size() / 3) result.push_back(candidate2);
    return result;
  }
};