169. 多数元素

;(function () {
  /**
   * 169. 多数元素
   * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
   * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
   *
   * 输入：nums = [3,2,3]
   * 输出：3
   *
   * 输入：nums = [2,2,1,1,1,2,2]
   * 输出：2
   *
   * 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
   *
   */

  function majorityElement(nums: number[]): number {
    // 方法一：排序法
    // // 思路： （如果满足数组非空且总是存在多数元素的话）数组排序，数组最中间的那个数字就是的
    // let index = Math.floor(nums.length/2);
    // return nums.sort((a, b) => a - b)[index]

    // 方法二：计数法
    // type typeObj = {
    //     [prop: string]: number
    // }
    // let temp: typeObj = {};
    // let rtn: number = -1;
    // for(let i = 0; i < nums.length; i++) {
    //     temp[nums[i]] ? temp[nums[i]]++ : temp[nums[i]] = 1;
    // }
    // for(let k in temp) {
    //     temp[k] > nums.length/2 ? rtn = +k : null;
    // }
    // return rtn

    // 方法三：摩尔投票法
    let rtnArr: number[] = []
    for (let i = 0; i < nums.length; i++) {
      let rtnLen = rtnArr.length
      if (rtnLen > 0) {
        rtnArr[0] !== nums[i] ? rtnArr.pop() : rtnArr.push(nums[i])
      } else {
        rtnArr.push(nums[i])
      }
    }
    return rtnArr[0]
  }

  let nums = [2, 2, 1, 1, 1, 2, 2]
  let nums2 = [3, 2, 3]
  console.log(majorityElement(nums))
  console.log(majorityElement(nums2))
})()