题目简介
不得不说,这题一上来On时间复杂度,O1空间复杂度直接封死了Hash表和两层循环想来想去没啥好方法。。看题解了
本题的核心思想就是将唯一出现的两个数字通过m来分隔开,然后再到分隔开的数组之间进行异或,直接可以得到数,看不懂的可以看下面的流程图和代码注解
结合以下注解观看更佳
我的理解
大概就是异或的结果是至少有一位不同的,我们通过对原数组循环异或,会得到题目中的仅有一个的那两个数的异或(也就是我们要得到的),我们将通过一个辅助变量m来获得他们之间的二进制不同位,只要得到了他,我们就可以将题目给的原数组,分割为两个分别包含我们想求得数字的数组,再对他们分别异或,由于其他都是两两成对的(异或为0),最后得到的必然就是我们想求的数字。
最后贴上我写的代码,大同小异,不得不感慨大佬的思路真厉害
class Solution {
public int[] singleNumbers(int[] nums) {
int x = 0,y = 0,n = 0,m = 1;
for(int num : nums){
n ^= num;
}
while((m & n) == 0){
m <<= 1;
}
for(int num : nums){
if((num & m) == 0){
x ^= num;
}else{
y ^= num;
}
}
return new int[]{x,y};
}
}