Single Number III
Source
- lintcode: Single Number III
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.
题解
题 Single Number 的 follow up, 不妨设最后两个只出现一次的数分别为 x1, x2
. 那么遍历数组时根据两两异或的方法可得最后的结果为 x1 ^ x2
, 如果我们要分别求得 x1
和 x2
, 我们可以根据 x1 ^ x2 ^ x1 = x2
求得 x2
, 同理可得 x_1
. 那么问题来了,如何得到x1
和x2
呢?看起来似乎是个死循环。大多数人一般也就能想到这一步(比如我...)。
这道题的巧妙之处在于利用x1 ^ x2
的结果对原数组进行了分组,进而将x1
和x2
分开了。具体方法则是利用了x1 ^ x2
不为0的特性,如果x1 ^ x2
不为0,那么x1 ^ x2
的结果必然存在某一二进制位不为0(即为1),我们不妨将最低位的1提取出来,由于在这一二进制位上x1
和x2
必然相异,即x1
, x2
中相应位一个为0,另一个为1,所以我们可以利用这个最低位的1将x1
和x2
分开。又由于除了x1
和x2
之外其他数都是成对出现,故与最低位的1异或时一定会抵消,十分之精妙!
Java
public class Solution {
/**
* @param A : An integer array
* @return : Two integers
*/
public List<Integer> singleNumberIII(int[] nums) {
int diff=0;
List<Integer> result = new ArrayList<Integer>();
for(int num: nums){
diff ^= num;
}
diff &= ~(diff-1);
int single1 = 0;
int single2 = 0;
for(int num: nums){
if((diff&num)==0){
single1^=num;
}
else{
single2^=num;
}
}
result.add(single1);
result.add(single2);
return result;
}
}