算法练习15：只出现一次的数字 II（leetcode 137）

题目

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

解法1：哈希表

遍历一遍，哈希表存储元素次数；再遍历哈希表，找出只出现一次的元素

var singleNumber = function(nums) {
    let map = new Map()
    for(let i = 0; i < nums.length; i++) {
        if(!map.has(nums[i])) {
            map.set(nums[i], 1)
        }else {
            map.set(nums[i], map.get(nums[i]) + 1)
        }
    }
    for(let [key, value] of map) {
        if(value == 1) return key
    }
};

• 空间复杂度: O( (n-1)/3 + 1 ) => O(n)
• 时间复杂度: O(n)

解法2：排序，遍历判断没有相邻重复的值

先对原数组从小到大排序，如果相邻两个数相等，说明它不是要的数，直接跳到当前位的后三位数继续判断，直到找到结果为止

var singleNumber = function(nums) {
  nums.sort((a, b) => a -b )
  console.log(nums)
  let len = nums.length
  let i = 0
  while(i!==len-1) {
      if(nums[i] === nums[i+1]) i += 3
      else return nums[i]
  }
  return nums[len - 1]
};

• 空间复杂度: O(1）
• 时间复杂度: 不考虑排序操作的话，O(n)；考虑排序的话，一般O(nlogn)

解法3：数学求和与差值方式

1. 使用set的方式，对原数组去重
2. 将去重后的的所有数求和setSum
3. 将原数组所有数求和allSum
4. 因为除了那单个数x，其他数都出现3次，所以 3* setSum = allSum + x*2
5. 利用这个公式：x = (setSum*3 - allSum) /2即可得出结果

var singleNumber = function(nums) {
  let set = new Set(nums)
  function sum(arr) {
      return arr.reduce((cur,val) => cur + val)
  }
  const setSum = sum([...set])
  const allSum = sum(nums)
  return (setSum*3 - allSum)  / 2
};

• 空间复杂度: O(n)
• 时间复杂度: O(n)

解法4：位运算

遍历所有数的二进制值，比如第i位，将所有数的第i位的二进制位数相加，如果对3求模不为0，则代表那单个数这位上的二进制不为0，补1
对每一位二进制都做这个处理，最后得到的结果就是那个单个数。

• 求某个数的第i位的二进制，右移i位，再与1相与：x >> i & 1
• 将第i位的最终结果保存到结果，1左移i位，再与之前结果相或: 1 << i | res

复杂度：

• 空间复杂度: O(1)
• 时间复杂度: O(32n) => O(n)

var singleNumber = function(nums) {
  let res = 0;
  // i用来记录当前的二进制位数，从最后一位开始
  for(let i = 0; i < 32; i++) {
    let count = 0; // 用于记录所有数的当前位二进制的和
    // j用来记录当前遍历到数
    for(let j = 0; j < nums.length; j++) {
      // 当前位右移i位，再与1相与，可以得到第i位上的二进制数
      if(nums[j] >> i & 1) {
        count++;
      }
    }

    // 和对3求模，得到的就是那个单个数第i位的二进制数
    if(count % 3 !== 0) {
      // res为之前的数，1是用来保证
      res = res | (1 << i)
    }
  }
  return res;
};