169. Majority Element

[soonlive]

169. Majority Element

  /**
   * @param {number[]} nums
   * @return {number}
   */
  var majorityElement = function (nums) {
    return majority(nums, 0, nums.length - 1);
  };

  function majority(nums, left, right) {
    if (left === right) {
      return nums[left];
    }
    var mid = left + ((right - left) >> 1);
    var lm = majority(nums, left, mid);
    var rm = majority(nums, mid + 1, right);
    if (lm === rm) {
      return lm;
    }

    var lcount = 0;
    var rcount = 0;
    nums.slice(left, right + 1).forEach(function (n) {
      if (lm === n) {
        ++lcount;
      }
      if (rm === n) {
        ++rcount;
      }
    });
    return lcount > rcount ? lm : rm;
  }