leetcode 练级 - 只出现一次的数字 升级版

题目

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



说明：

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



示例 1:

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

输出: 3



示例 2:

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

输出: 99



来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/single-number-ii



解题思路

参考了别人的一些实现方法，感觉用位运算来实现，很巧妙，真的很佩服第一个想到这种解法的人，哈哈。。。 异或、与、否等运算相结合，参考了别人的思路，下面自己再简单走一遍，学习记录下

主要用到下面几个运算规律：

x^0 =x

x^x =0

x& ~x =0

x& ~0 =x



具体看下执行过程

数组中某个数x第一次出现时，初始值a = 0, b = 0，所以a = (a^x)& ~b=x, b = (b^x)& ~a = 0

数组中某个数x第二次出现时，初始值a = x, b = 0，所以a = (a^x)& ~b=0, b = (b^x)& ~a = x

数组中某个数x第三次出现时，初始值a = 0, b = x，所以a = (a^x)& ~b=0, b = (b^x)& ~a = 0



所以数组中同一个数经过出现三次后，经过这样的位运算，a和b都恢复为0了

根据位运算的交换律，出现三次的数，a和b都归为0，出现一次的数，最后等于a了，最后return a就可以了



代码实现

var singleNumber = function(nums) {
    let a = 0
        b = 0
    for (let i = 0; i < nums.length; i++) {
         a = (a ^ nums[i]) & ~b
         b = (b ^ nums[i]) & ~a 
    }
    return a
};