[LintCode/LeetCode] Single Number III

116 查看

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): 去掉最后一个1;
n & (-n): 保留最后一个1;
n & (~(n-1)): 保留最后一个1;
Integer.highestOneBit(n): 保留第一个1;

这道题在LC论坛里参考了huangjingshu和zhiqing_xiao两位仁兄的解法。思想是:
将A中所有的数进行异或运算。不同的两个数异或的结果diff,一定至少有一位为1。我们只保留diff中的一个1,可以是第一个1,也可以是最后一个1,假设这个1在第i位好了!
然后再次将A中所有的数numdiff相与:
num & diff的结果为diff,说明这些num的第i位是1:将numres0异或后存入res0,这样最后异或出来的结果就是两个single number中第i位是1的那个;
同理,若num & diff的结果为0,说明这些num的第i位是0:将numres1异或后存入res1,这样最后异或出来的结果就是两个single number中第i位是1的那个。
最后,将res1res0存入res数组,返回。

Solution

public class Solution {
    public List<Integer> 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<Integer> res = new ArrayList();
        res.add(res0);
        res.add(res1);
        return res;
    }
}

2018 - 知识虫 - 我的知识库 渝ICP备16002641号-2

渝公网安备 50010702501581号