leetcode刷题（数组·位异或）16— 只出现一次的数字 II

137. 只出现一次的数字 II

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

分析

这个代码是参考leetcode题解写的，我按照我的理解分析一下代码的由来。
此代码时间复杂度为O(n),空间复杂度为O(1)。

先分析题目：非空整数数组、除一个元素出现一次外，其余元素均出现三次——找出出现一次的元素。
即：我们需要区分出现一次和三次的元素，但在我们进行遍历的时候，是需要一个一个遍历的，故除了会检测到出现一次和三次的元素，还会存在中间状态：出现两次的元素。因为一共有三种状态，故用两位二进制数来表示：01，10，00分别代表出现一次、两次和三次的元素的状态；
（由于与或、异或均满足交换律，故我们不需要考虑原数组的乱序问题）
我们需要找到一种运算方式满足：
00遇到1个1变成01，01遇到1个1变成10，10遇到1个1变成00，遇到0不变

真值表

XY	Z	Xnew	Ynew
00	0	0	0
01	0	0	1
10	0	1	0
00	1	0	1
01	1	1	0
10	1	0	0

XY:原始状态
Z：输入值
我在这里的理解是：1是个泛指，从三个状态的表示可以看出Xnew = 1表示出现两次的数（当然由于是乱序数组，前方输入若是不满足整三使状态清零的话，此处不表示出现两次的数）；同理，Ynew = 1表示出现一次的数。
计算逻辑表达式：（将Ynew = 1的行相加）
Ynew = (～X)·Y·(~Z)+ (～X)·(~Y)·Z = (～X)·[Y·(~Z) + (~Y)·Z] = (～X)·(Y^Z)
Xnew = (～Ynew)·(X^Z)

class Solution {
    public int singleNumber(int[] nums) {
        int sinceOne = 0,sinceTwo = 0;
        // String resOne,resTwo;
        for(int num : nums){
            // resOne = Integer.toBinaryString(sinceOne);
            // resTwo = Integer.toBinaryString(sinceTwo);
            // System.out.println("resone:"+resOne);
            // System.out.println("restwo:"+resTwo);
            // System.out.println(" ");
            sinceOne = ~sinceTwo & (sinceOne ^ num);
            sinceTwo = ~sinceOne & (sinceTwo ^ num);
            
        }
        // resOne = Integer.toBinaryString(sinceOne);
        // resTwo = Integer.toBinaryString(sinceTwo);
        // System.out.println("resone:"+resOne);
        // System.out.println("restwo:"+resTwo);
        return sinceOne;
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。