原题链接:
https://leetcode.cn/problems/single-number-iii/description/

解法1: 位运算 分组异或

要求是线性时间复杂度的算法且仅使用常量额外空间来解决此问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
    分组异或
    先对nums中所有数进行异或得到sum  根据题意以及异或运算的性质 sum两个不同数的异或值(其他两个相同的数直接被抵消了)
    然后取sum二进制位的任意为1 的一位  根据异或运算性质该位为1 说明 对于两个不同的数在第k位的二进制为的表示不同
    然后对原nums中的数 第k位为0或1的分别进行异或运算 这样相同的数仍然会消去(反证法 思想如果k位不相同那么数必定不同 就一定不可能在同一个组内进行运算)
     最后得到就是两个不同的数
*/
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        // 先进一次异或运算 得到sum
        int sum = 0;
        for(int x: nums){
            sum ^= x;
        }
        
        int k = 0;
        // 找到任意的第k位
        for(int i = 31 ; i >= 0 ; i--){
            if((sum >> i) & 1 == 1){
                k = i;
                break;
            }
        }

        vector<int>ans(2,0);

        for(int x : nums){
            if((x >> k) & 1){
                ans[1] ^= x;
            }else{
                ans[0] ^= x;
            }
        }

        return ans;
    }
};