Single Number III

今天刚看到一个好玩的题.

给n个数,其中有两个数字出现过一次, 另外数字都出现过两次. 找出这两个数.要求time: O(n), space: O(1).

思路是这样的: 首先用一个变量diff, 对每个数做xor, 这样得到的diff里面只有这两个数字中bit不同的位代表的数字,diff是一定不为0的, 因为这两个数不同, 不然所有数都出现两次了, 其他的数字因为出现两次, 都被xor删除了, 剩下的两个数字的不同位的代表的数. diff虽然表示了两个数中不同位, 但是它不能用来直接计算, 因为如果用它判断这两个数, 不能确保判断出两个数的位是留下的位. 所以这里我们要取diff中的最右边的为1的位. 这里用的方法是:

int rightBit = diff & -diff;

因为java中负数用的是two complement, 所以以上的公式可以返回diff中最右边的为1的位代表的数字. 比如:

这个1的意义是, 我们需要找的两个数可以通过这个1来区别. 所以我们通过这个1,可以把数组分成两组, 每组都包含一个我们要找的数, 因为其他数都是出现两次, 所以留下的就是最后我们要找的答案

Code:

public class Solution {
    public int[] singleNumber(int[] nums) {
        if (nums.length == 0 || nums == null)
            return null;
        int diff = 0;
        for(int i : nums)
            diff ^= i;
        int rightBit = diff & -diff;
        int[] result = new int[]{0,0};
        for(int i : nums){
            if((i & rightBit) == 0)
                result[0] ^= i;
            else
                result[1] ^= i;
        }
        return result;
    }
}