229. 多数元素 II

;(function () {
  /**
   * 229. 多数元素 II
   * 给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
   *
   * 输入：nums = [3,2,3]
   * 输出：[3]
   *
   * 输入：nums = [1]
   * 输出：[1]
   *
   * 输入：nums = [1,2]
   * 输出：[1,2]
   *
   * 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
   */

  function majorityElement(nums: number[]): number[] {
    // 方法一：摩尔投票法 --- 抵消阶段和计数阶段
    // // 分析：
    // // 1. 超过 ⌊ n/3 ⌋ 次的元素，则表示返回的数组最多只有 2 个元素。
    // // 2. 遍历数组，多方混战。战斗结果一定只有最多两个阵营幸存，其他阵营被歼灭。数组中的数字即代表某士兵所在的阵营。
    // if (nums.length < 3) {
    //     return [...Array.from(new Set(nums))]
    // }
    // let aArr: number[] = [];
    // let bArr: number[] = [];
    // for(let i = 0; i < nums.length; i++) {
    //     let cur = nums[i]
    //     // 1. 属于AB阵营的兵力，则累加
    //     if ( aArr.includes(cur)) {
    //         aArr.push(cur);
    //         continue;
    //     }
    //     if ( bArr.includes(cur)) {
    //         bArr.push(cur);
    //         continue;
    //     }
    //     // 2. 新兵力不属于AB阵营，则混战
    //     if(aArr.length > 0 && bArr.length > 0) {
    //         aArr.pop()
    //         bArr.pop()
    //     } else if (aArr.length === 0 ){
    //         aArr.push(cur)
    //     } else {
    //         bArr.push(cur)
    //     }
    // }
    // let rtnArr: number[] = [];
    // let len = nums.length / 3;
    // let count1 = 0;
    // let count2 = 0;
    // nums.forEach(i => {
    //     i === aArr[0] && count1++;
    //     i === bArr[0] && count2++;
    // })
    // count1 > len && rtnArr.push(aArr[0]);
    // count2 > len && rtnArr.push(bArr[0]);
    // return rtnArr

    // 方法一：摩尔投票法简化版
    // // 分析：
    // // 1. 超过 ⌊ n/3 ⌋ 次的元素，则表示返回的数组最多只有 2 个元素。
    // // 2. 遍历数组，多方混战。战斗结果一定只有最多两个阵营幸存，其他阵营被歼灭。数组中的数字即代表某士兵所在的阵营。
    // // if (nums.length < 3) {
    // //     return [...Array.from(new Set(nums))]
    // // }
    // // 配对阶段
    // let a = nums[0], aCount = 0;
    // let b = nums[0], bCount = 0;
    // nums.forEach(item => {
    //     if (a === item) {
    //         aCount++;
    //         return
    //     }
    //     if (b === item) {
    //         bCount++;
    //         return
    //     }
    //     if (aCount === 0) {
    //         a = item;
    //         aCount++;
    //         return
    //     }
    //     if (bCount === 0) {
    //         b = item;
    //         bCount++;
    //         return
    //     }
    //     aCount--;
    //     bCount--;
    // })
    // // 计数阶段
    // let rtnArr: number[] = [];
    // let len = nums.length / 3;
    // let count1 = 0;
    // let count2 = 0;
    // nums.forEach(i => {
    //     i === a && aCount > 0 && count1++;
    //     i === b && bCount > 0 && count2++;
    // })
    // count1 > len && rtnArr.push(a);
    // count2 > len && rtnArr.push(b);
    // return rtnArr

    // 方法二： 遍历法 / new Map()
    // new Map -- set: count++, get: count > n/3
    type typeObj = {
      [prop: string]: number
    }
    let obj: typeObj = {}
    let rtnArr: number[] = []
    nums.forEach((item) => {
      obj[item] ? obj[item]++ : (obj[item] = 1)
    })
    for (let k in obj) {
      obj[k] > nums.length / 3 ? rtnArr.push(+k) : null
    }
    return rtnArr
  }

  let nums = [2, 2, 1, 1, 1, 2, 2]
  let nums2 = [3, 2, 3]
  let nums3 = [2, 2]
  let nums4 = [1]
  let nums5 = [0, 0, 0]
  // console.log(majorityElement(nums))
  // console.log(majorityElement(nums2))
  // console.log(majorityElement(nums3))
  // console.log(majorityElement(nums4))
  console.log(majorityElement(nums5))
})()