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

摩尔投票法

大于 n/3 的数最多有三个

• 时间复杂度O(n)，空间复杂度O(1)
• Runtime: 72 ms, faster than 97.23%
• Memory Usage: 42.3 MB, less than 20.16%

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var majorityElement = function(nums) {
  let count1 = 0;
  let count2 = 0;
  let candidate1;
  let candidate2;
  
  for (let val of nums) {
    if (candidate1 === val) {
      count1++;
    } else if (candidate2 === val) {
      count2++;
    } else if (count1 === 0) {
      candidate1 = val;
      count1++;
    } else if (count2 === 0) {
      candidate2 = val;
      count2++;
    } else {
      count1--;
      count2--;
    }
  }
  
  count1 = 0;
  count2 = 0;
  for (let val of nums) {
    if (candidate1 === val) {
      count1++;
    }
    if (candidate2 === val) {
      count2++;
    }
  }
  
  const res = [];
  const len = parseInt(nums.length / 3);
  if (count1 > len) res.push(candidate1)
  if (count2 > len) res.push(candidate2);
  return res;
};