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?
Credits:
Special thanks to for adding this problem and creating all test cases.x &= -x 是用了树状数组中的lowbit。
1 class Solution { 2 public: 3 vector singleNumber(vector & nums) { 4 int x = 0; 5 for (auto n : nums) x ^= n; 6 int tmp = x, idx = 0; 7 x &= -x; 8 int a = 0, b = 0; 9 for (auto n : nums) {10 if (n & x) a ^= n;11 else b ^= n;12 }13 return {min(a, b), max(a, b)};14 }15 };