136. 只出现一次的数字

;(function () {
  /**
   * 136. 只出现一次的数字
   * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
   *
   * 说明：
   * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
   *
   * 输入: [2,2,1]
   * 输出: 1
   *
   * 输入: [4,1,2,1,2]
   * 输出: 4
   *
   */

  function singleNumber(nums: number[]): number {
    // 方法一： 遍历数组 -- 两次循环，效率不高
    // type objType = {
    //     [prop: string]: number
    // }
    // let obj: objType = {};
    // let rtn: number = 0;
    // nums.forEach((item, index) => {
    //     obj[item + ''] === undefined ? obj[item + ''] = 1 : obj[item + '']++
    // })
    // for(let k in obj) {
    //     if (obj[k] === 1) {
    //         rtn = +k
    //         break
    //     }
    // }
    // return rtn

    // 方法二：效率也不是很高
    // 数组先排序，然后遍历数组（单个元素如果和前后都不相等，则判定当前元素唯一）
    // let newNums = nums.sort((a, b) => a - b)
    // let rtn = 0;
    // for(let k = 0; k < newNums.length; k++) {
    //     if (newNums[k] !== newNums[k + 1] && newNums[k] !== newNums[k - 1]) {
    //         rtn = newNums[k]
    //         break;
    //     }
    // }
    // return rtn

    // 方法三：异或（位运算）（官网提供）
    // 不需要额外空间的方法，就往位运算上想
    let single = 0
    for (let i in nums) {
      single ^= nums[i]
    }
    return single

    // 方法四： 哈希？
  }

  let arr = [2, 2, 1]
  let arr2 = [4, 1, 2, 2, 1]
  console.log(singleNumber(arr))
  console.log(singleNumber(arr2))
})()