LeetCode[位运算] - #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

 简单测试程序

 

你可能感兴趣的