260. 只出现一次的数字 III

image-20211030142711412

解题思路：

​ 这题首先最简单的方法肯定是遍历+哈希表记录次数的方法，主要说第二种优化了空间复杂度的方法。

  • 遍历nums的所有元素并进行异或处理，得到temp

  • 获取temp的最低位1，由此就可以将恰好出现一次的两个元素分成两组

    • temp^(-temp)的方法获取最低位1（-temp其实对应二进制的取反+1，若原位为1则变为0，+1后&为1，若原位为0则变为1，+1后向前进位且&结果为0，因此恰好可以获取到最低位1）
    • 设定lowOne=1，while(lowOne&temp==0) lowOne<<=1; （也就是逐步左移判断）

  • 遍历nums的所有元素，根据得到得到lowOne*nums[i]判断所在组，同组的所有元素再进行异或操作，就能得到两个结果，返回即可。

以下是C++代码：

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
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        //用最低位1将得到的结果分成两个部分
        int temp=0;
        int length=nums.size();
        for(int i=0;i<length;i++){
            temp^=nums[i];
        }

        //计算最低位1的两种方法
        //方法1
        //int lowOne=temp==INT_MIN?temp:temp&(-temp); 

        //方法2
        int lowOne=1;
        while((lowOne&temp)==0) lowOne<<=1;

        int ans1=0,ans2=0;
        for(int i=0;i<length;i++){
            if(nums[i]&lowOne){
                ans1^=nums[i];
            }
            else{
                ans2^=nums[i];
            }
        }
        return {ans1,ans2};
    }
};