LeetCode[位运算] - #137 Single Number II

原题链接：#137 Single Number II 

要求：

给定一个整型数组，其中除了一个元素之外，每个元素都出现三次。找出这个元素

注意：算法的时间复杂度应为O(n)，最好不使用额外的内存空间

 

难度：中等

 

分析：

与#136类似，都是考察位运算。不过出现两次的可以使用异或运算的特性 n XOR n = 0, n XOR 0 = n，即某一位上出现偶数次1将该位置为0，出现奇数次1将该位置为1，这样扫一遍数组即可得到结果。

 

类似的，对于本题出现三次的情况，我们需要构造一个与异或类似的运算，使某一位出现三次1时置为0，出现3n+1次1时置为1。取三个整型值ones, twos, threes，均初始化为0，分别用于记录某一位出现1的次数。为简单起见，设输入数组M = {1,1, ... 1}, M中元素个数为m，则对于每一个输入项M[i]，令:

 

twos = twos | ones & M[i]

ones = ones ^ M[i]

threes = ones & threes

ones = ones & ~threes // 当threes为1时将ones和twos置为0

twos = twos & ~threes

 

故m=3n时，threes = 1, m=3n+1时，ones = 1。

 

解决方案：

Java - 248ms

public int singleNumber(int[] A) {
        if(A.length==0) {
            return 0;
        }
        int ones=0, twos=0, threes=0;
        for (int i=0;i<A.length;i++){
            twos |= ones & A[i];
            ones = ones ^ A[i];
            threes = ones & twos;
            ones = ones & ~threes;
            twos = twos & ~threes;
        }
        return ones;
    }

 简单测试程序