Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

如果是其他元素出现两次,某一个元素出现一次,那么直接用xor的方法就可以找到这一一个数。因为x^x = 0.
这类问题还有变体,但是本质都是一样的,利用bitwise的operator,统计每一位出现的次数,比如上题如果某一位上整个array 1出现的个数是奇数个(表现为xor的结果为1,奇数个1xor为1,偶数个则为0),那么那个单独出现的的数的对应那一位就是一,反之则是0。

本题不一样之处在于所有其他元素每个都出现三次,那么xor得出的结果是不行的,但是只要稍微变化一下,只要我们累加1出现的个数,然后除以3(xor相当于除以2的余数),那么得出的值(1或者0)就是那个单独的数的相应位数了。

代码可以有两种,第一种是用两个变量ones和twos,ones只记录出现一次的数的1的个数(xor),twos只记录出现两次的数的1的个数(如果出现两次1,那么twos被设为1),逻辑如下:
1.x是新的元素
2.twos |= ones & x; //x如果是第一次出现,那么x的bit representation(如果是1的话)不会被放进twos里。因为ones里没有twos的representation,&以后就没有了,所以x第一次出现不会影响twos的结果。而如果ones里和twos里都有1,那么说明这个1出现了三次了,这个再最后step4,5,6会处理。如果x是第二次出现,那么ones里就已经有这一位的bit representation,这样twos就会被设为1.
3.ones = x^ones;//如果x第一次出现,那么x被xor进ones中,如果x第二次出现,x^x=0,x又被从ones里剔除出去了。如果x中的1第三次出现的话ones又会被设为1,但是在4,5,6三步里会处理。
4,5,6
bitmask = ~(ones & twos);
twos &= bitmask;
ones &= bitmask;
这三步就保证了如果x是第三次出现,他们会被从twos和ones里都去除掉。

所以上面的六步就保证了,如果1出现1次,那么ones会记录下,如果1出现两次,ones中会被移除出去,记录在twos中,如果出现三次,则ones和twos中都被移除出去了。所以说到最后所有的数被扫描完以后,ones中就是我们需要的值了。

public class Solution {
    public int singleNumber(int[] A) {
        int ones = 0; // 1st time appearance
        int twos = 0; // 2nd time appearance
        for (int i = 0; i < A.length; i++) {
            twos = twos | (ones & A[i]);// calculate 2nd appearance based on previous 1st appearance result
            ones = ones ^ A[i];
            int bitMask = twos & ones;// filter out 3rd appearance. if both ones and twos record a 1, it is 3rd appearance
            ones = (~bitMask) & ones; 
            twos = (~bitMask) & twos; // also need to remember to remove 1s from twos, because twos use | so it will not clear those appeared 3rd from itself by the first statement
        }
        return ones;
    }
}

更straight forward的代码是直接将所有数组中的数每一位的1加起来,然后除以三,得出的余数就是那个单独出现的数的对应位数了。注意对于负数如果用下面的方法的话要注意不能用>0或者<0而应该用!=0来判断。

public class Solution {
    public int singleNumber(int[] A) {
        if (A.length == 0)
            return 0;
        else
        {
            int result = 0;
            //first deal with the numbers
            for (int bit = 0; bit < 32; bit++)
            {
                int bitResult = 0;
                int mask = (0x1 << bit);
                for (int i= 0; i < A.length; i++)
                {
                    if ( (mask & A[i]) != 0) //use != 0 to accommodate negative numbers
                        bitResult++;
                }
                if ((bitResult % 3) != 0) //use != 0 to accommodate negative numbers
                    result |= mask;
            }
            /*
            int sign = 0;
            for (int i = 0 ; i < A.length; i++)
            {
                if (A[i] < 0)
                {
                    sign++;
                }
            }
            if (sign%3 > 0)
                result *= -1;
            */
            //then deal with the sign
            return result;
        }
    }
}

How about we changed question to: There are two numbers that appear once while all the rest appear twice? We can xor all the numbers but the result will be the xor of the two single numbers. With this xor result, we can be sure that those one bits in the result are different bits in the two numbers we are looking for. So we can simply pick one bit, put all those numbers with 1 on that bit to one side and those with 0 on that bit on the other. Those two split array will have only one number that appear once, then we can simply use xor to find the result.

See comment for detail

public class Solution {
    public int singleNumber(int[] A) {
        int ones = 0;
        int twos = 0;
        int threes = 0;
        for (int i = 0; i < A.length; i++) {
           twos |= ones & A[i]; //bit appears more than twice
           ones ^= A[i]; //bit appreas 1 or 3 times
           threes = ones & twos; // bit appears 3 times
           ones = (~threes & ones); // remove three from ones
           twos = (~threes & twos); // remove three from twos
        }
        return ones;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s