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?
可以先排序，然后把单个的挑出来。但是这个的时间复杂度不太好，要先排序。
var singleNumber = function(nums) {
nums.sort();
var result = [];
for (var i = 1; i<nums.length;i++) {
if ((nums[i]^nums[i-1])!==0) {
result.push(nums[i-1]);
} else {
i++;
}
}
if (result[1]===undefined)
result[1] = nums[nums.length-1];
return result;
};
还有一种方法，还是使用异或
先遍历一遍数组，把所有值的异或取到，这样最后得到的结果就是我们需要的两个数的异或值，这个值中1所在的位代表这两个数在这位是不同的，一个是1一个是0。
我们从是1的位中随便挑一个，其他位都变回0。用这个数和数组里每个数进行与，这位不是1的数的结果都是0。这样就可以把这个数组里的数分为2部分，我们要的这两个数正好就分别在这两部分里，这两部分里其他的数都是成对的。于是这两部分里的数分别全部异或起来，就得到了我们想要的两个数。
var singleNumber = function(nums) {
var diff = 0;
var result = [];
for (var i = 0;i < nums.length;i++) {
diff = diff ^ nums[i];
}
diff &= -diff;
for (i = 0;i < nums.length;i++) {
if ((nums[i]&diff)===0)
result[0]^=nums[i];
else
result[1]^=nums[i];
}
return result;
};
这个方法的时间复杂度是O(2n)。
