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?
Solution 1:Use xor to get the value of num1 XOR num2, find a bit not zero. use this bit to seperate the array into 2 groups (bit=1 and bit=0). So num1 and num2 will be separate. Then do xor to each group to find the num 1 and num 2.
public class Solution {
public int[] singleNumber(int[] nums) {
int xor=0;
for (int x: nums) xor^=x;
int i=0;
while ((xor>>i&1)==0) i++;
int[] res=new int[2];
for (int x: nums) {
if ((x>>i&1)==0) res[0]^=x;
else res[1]^=x;
}
return res;
}
}
没有评论:
发表评论