[LintCode/LeetCode] Single Number III

lanffy 發(fā)布于2019-08-14 15:33 / 2939人閱讀

摘要：去掉最后一個(gè)保留最后一個(gè)保留最后一個(gè)保留第一個(gè)這道題在論壇里參考了和兩位仁兄的解法。思想是將中所有的數(shù)進(jìn)行異或運(yùn)算。不同的兩個(gè)數(shù)異或的結(jié)果，一定至少有一位為。最后，將和存入數(shù)組，返回。

Problem

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.

Note

n & (n-1): 去掉最后一個(gè)1；
n & (-n): 保留最后一個(gè)1；
n & (~(n-1)): 保留最后一個(gè)1；
Integer.highestOneBit(n): 保留第一個(gè)1；

這道題在LC論壇里參考了huangjingshu和zhiqing_xiao兩位仁兄的解法。思想是：
將A中所有的數(shù)進(jìn)行異或運(yùn)算。不同的兩個(gè)數(shù)異或的結(jié)果diff，一定至少有一位為1。我們只保留diff中的一個(gè)1，可以是第一個(gè)1，也可以是最后一個(gè)1，假設(shè)這個(gè)1在第i位好了！
然后再次將A中所有的數(shù)num和diff相與：
若num & diff的結(jié)果為diff，說明這些num的第i位是1：將num與res0異或后存入res0，這樣最后異或出來的結(jié)果就是兩個(gè)single number中第i位是1的那個(gè)；
同理，若num & diff的結(jié)果為0，說明這些num的第i位是0：將num與res1異或后存入res1，這樣最后異或出來的結(jié)果就是兩個(gè)single number中第i位是1的那個(gè)。
最后，將res1和res0存入res數(shù)組，返回。

Solution

public class Solution {
    public List singleNumberIII(int[] A) {
        int diff = 0;
        for (int num: A) {
            diff ^= num;
        }
        //diff &= -diff;
        diff &= ~(diff-1);
        int res0 = 0, res1 = 0;
        for (int num: A) {
            if ((diff & num) == diff) res0 ^= num;
            else res1 ^= num;
        }
        List res = new ArrayList();
        res.add(res0);
        res.add(res1);
        return res;
    }
}