多数元素

LeetCode-169

var majorityElement = function (nums = []) {
  // 方法一、排序，取中间那个值
  // nums.sort((a, b) => a - b) // sort()方法的时间复杂度是O(nlogn)
  // return nums[Math.floor(nums.length / 2)]

  // 方法二、摩尔投票法(Moore Voting)是一种用于找出数组中出现次数超过一半的元素的算法，其时间复杂度为O(n)，空间复杂度为O(1)
  // 思想：对于数组中任意两个不同元素a和b(a !== b)，如果它们同时从数组中移除，那么剩余部分数组中多数元素依然不变
  let res = nums[0], count = 1
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] === res) {
      count++
    } else {
      count--
      if (count === 0) {
        res = nums[i]
        count = 1
      }
    }
  }
  return res
}