[LintCode] 84 Single Number III 解题报告

Description
Given 2*n + 2 numbers, every numbers occurs twice except two, find them.



Example
Given [1,2,2,3,4,4,5,3] return 1 and 5



Challenge
O(n) time, O(1) extra space..



思路
这题有2个落单的数字。比如说这个数组里的数字是a a b b c d e e f f，c和d是两个落单数字。那么当我们把数组里所有的数字都xor以后，所有成对的数字都cancel out了，那么就剩下来c ^ d。
我们知道c != d。所以如果从二进制的表示来看，c和d一定至少在某一位i，一个是0，一个是1。
那么我们可以想办法把整个数组分成两组：一组是某一位都是0的数字，一组是某一位都是1的数字。

举个例子，xor = a ^ a ^ b ^ b ^ c ^ d ^ e ^ e ^ f ^ f = c ^ d的值如果是110100。那么我们知道，c和d在所有1的位置的值都是相异的。
我们可以用lastBitWithOne = xor - (xor & (xor - 1))来求出最后那个1的位置，上式的结果是100。

遍历数组，我们用A[i] & lastBitWithOne来判断A[i]在这一位上是不是0。那么我们就可以把所有的数字分成两组，用Single Number I的方法来求出最后的解。



Code

public class Solution {
    /**
     * @param A : An integer array
     * @return : Two integers
     */
    public List<Integer> singleNumberIII(int[] A) {
        // write your code here
        
        int xor = 0;

        for (int i = 0; i < A.length; i++) {
            xor ^= A[i];
        }
        
        int lastBitWithOne = xor - (xor & (xor - 1));
        
        int group0 = 0;
        int group1 = 0;
        
        for (int i = 0; i < A.length; i++) {
            if ((lastBitWithOne & A[i]) == 0) {
                group0 ^= A[i];
            }
            else {
                group1 ^= A[i];
            }
        }
        
        List<Integer> result = new ArrayList<>();
        result.add(group0);
        result.add(group1);
        
        return result;
    }
}