260. Single Number III

发表于 | 分类于

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

解法1： Bit Manipulation

这题挺好的。思维很巧妙。
首先还是要用XOR， 如果我们先把所有数字XOR一遍，那么结果就是A ^ B. 其中A，B就是我们要找的两个数。而这个结果一定不是0.那么如果我们随便找一个setbit， 就可以把原来的数组分成这个bit被set和不被set的两组。要求的数一定分别在这两组里面。对每一组分别求XOR就可以得到要求的结果。
其中求一个number的一个bit可以用一个小技巧

1
number & (-number)

可以得到rightmost setbit

lang: java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[] singleNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        int[] res = new int[2];
        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }
        int setBit = xor & (-xor);
        for (int num : nums) {
            if ( (num & setBit) == 0) {
                res[0] ^= num;
            } else {
                res[1] ^= num;
            }
        }
        return res;        
    }
}