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?
可以先排序，然后把單個(gè)的挑出來(lái)晶通。但是這個(gè)的時(shí)間復(fù)雜度不太好，要先排序伺帘。
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;
};
還有一種方法，還是使用異或
先遍歷一遍數(shù)組菱农，把所有值的異或取到垂睬，這樣最后得到的結(jié)果就是我們需要的兩個(gè)數(shù)的異或值，這個(gè)值中1所在的位代表這兩個(gè)數(shù)在這位是不同的尊蚁，一個(gè)是1一個(gè)是0。
我們從是1的位中隨便挑一個(gè)侣夷，其他位都變回0横朋。用這個(gè)數(shù)和數(shù)組里每個(gè)數(shù)進(jìn)行與，這位不是1的數(shù)的結(jié)果都是0百拓。這樣就可以把這個(gè)數(shù)組里的數(shù)分為2部分琴锭，我們要的這兩個(gè)數(shù)正好就分別在這兩部分里，這兩部分里其他的數(shù)都是成對(duì)的衙传。于是這兩部分里的數(shù)分別全部異或起來(lái)决帖，就得到了我們想要的兩個(gè)數(shù)。
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;
};
這個(gè)方法的時(shí)間復(fù)雜度是O(2n)蓖捶。
