229. Majority Element II

[soonlive]

229. Majority Element II

参考：
Boyer–Moore majority vote algorithm
http://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html

  /**
   * @param {number[]} nums
   * @return {number[]}
   */
  var majorityElement = function (nums) {
    var count1 = 0;
    var count2 = 0;
    var candidate1, candidate2;
    var result = [];

    for (var i = 0; i < nums.length; i++) {
      var num = nums[i];
      if (num === candidate1) {
        ++count1;
      } else if (num === candidate2) {
        ++count2;
      } else if (count1 === 0) {
        candidate1 = nums[i];
        ++count1;
      } else if (count2 === 0) {
        candidate2 = nums[i];
        ++count2;
      } else {
        --count1;
        --count2;
      }
    }

    count1 = 0;
    count2 = 0;

    nums.forEach(function (num) {
      if (candidate1 === num) {
        ++count1;
      }
      if (candidate2 === num) {
        ++count2;
      }
    });

    if (count1 > (nums.length / 3)) {
      result.push(candidate1);
    }

    if (count2 > (nums.length / 3)) {
      result.push(candidate2);
    }

    return result;
  };