260. 只出现一次的数字 III#

1
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。
2

3
找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
4

5
进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
6

7

8

9
示例 1：
10

11
输入：nums = [1,2,1,3,2,5]
12
输出：[3,5]
13
解释：[5, 3] 也是有效的答案。
14
示例 2：
15

16
输入：nums = [-1,0]
17
输出：[-1,0]
18
示例 3：
19

20
输入：nums = [0,1]
21
输出：[1,0]
22
提示：
23

24
2 <= nums.length <= 3 * 104
25
-231 <= nums[i] <= 2^31 - 1
26
除两个只出现一次的整数外，nums 中的其他数字都出现两次

1
class Solution {
2
public:
3
    vector<int> singleNumber(vector<int>& nums) {
4
        int sum = 0;
5
        for (int i : nums) sum ^= i;
6
        int k = -1;
7
        for(int i = 31; i >= 0 && k == -1; i--) {
8
            if (((sum >> i) & 1) == 1) k = i;
9
        }
10
        vector<int> ans(2);
11

12
        for (int i : nums) {
13
            if (((i >> k) & 1) == 1) ans[1] ^= i;
14
            else ans[0] ^= i;
15
        }
16
        return ans;
17
    }
18
};