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.
Example:
Input:[1,2,1,3,2,5]Output:[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?
Related Topics:
Bit Manipulation
Similar Questions:
Assume result numbers are a and b, and x is the result of XORing all the numbers.
For any bit 1 in x, it means a and b differs in this bit, and we can use this bit to group the numbers in two groups, one containing a and the other containing b.
x ^ (x & (x - 1)) is a trick that we can use to extract the lowest bit 1.
// OJ: https://leetcode.com/problems/single-number-iii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
vector<int> singleNumber(vector<int>& A) {
int x = 0;
for (int n : A) x ^= n;
int lb = x & -(unsigned)x, a = 0;
for (int n : A) {
if (n & lb) a ^= n;
}
return {a, x ^ a};
}
};