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
class Solution {
public: vector<int> singleNumber(vector<int>& nums) { int len = nums.size(); int abxor = 0; for (int i=0; i<len; i++) { abxor ^= nums[i]; } int mask = abxor & (~(abxor-1)); int a = 0; int b = 0; for (int i=0; i<len; i++) { if ((mask&nums[i]) == 0) { a ^= nums[i]; } else { b ^= nums[i]; } } return vector<int>({a, b}); }};