LeetCode 137. 只出现一次的数字 II

题目描述

难度：Middle

相关话题：位运算

给定一个非空 整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,3,2]
输出: 3

示例2:

输入: [0,1,0,1,0,1,99]
输出: 99

---

思路：

对于时间O(n)，空间O(1)的算法，需要编写一个状态机，当一个数出现3次，会抵消。

如果单变量使用^，只能抵消偶数次数，如果要3次抵消，必须要有2个变量同时^。

a=a^nums[i]

b=b^nums[i]

但仅仅这样两个变量完全一致，无法3次抵消。

因此还需要使用~，~的作用是将0变为1，1变为0，同时也可以将当前状态逆转。

a=(a^nums[i]) ~ b

b=(b^nums[i]) ~ a

例如一个数组[2,2,2,2,2,2]，它每次的a和b输出值为2,0，0,2，0,0，2,0，0,2，0,0，每3次置零。

/**
 * @ Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
  let a=0,b=0
  for(let n of nums){
    a=(a^n) & ~b
    b=(b^n) & ~a
  }
  return a
};