政子的博客

技术|学习|随笔

LeetCode-Set Mismatch

这道题虽然是 Easy，但是却被卡了很久，因为脑袋有些懵，一直以为只有相邻的数字会被改变，所以统计哪个数字没有出现的方法一直都有问题。

思路是先排序，然后顺序查找，如果某个数字之前的数字不连续出现，说明它之前从没出现过，则 result[1]就是它了，如果哪个数字和之前的数字相同，那就是重复的哪个数字，result[0]就是它了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        vector<int> result(2,0);
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++){
            if(nums[i]==result[1]+1){
                result[1]+=1;
            }
            if(i>0 && nums[i]==nums[i-1]){
                result[0]=nums[i];
            }
        }
        result[1]+=1;
        return result;
    }
};

当然，这样使用排序去解复杂度还是有些高（O(nlogn)），还可以使用更快的方法（O(n)）以及占用固定的空间（O(1)）。

这个方法主要的思路是：因为元素是从 1-n 之间的，所以可以不断交换元素的位置，将元素交换到正确的位置上（i->pos(i+1)），然后就再顺着找一遍，就可以找到不在合适位置上的元素，这样就可以得到答案了。

不过最开始写代码的时候又引入了一个非常大的 bug，就是如果没有代码int j=nums[i]-1;，就会陷入无限循环，因为 nums[i]的值被改变了，nums[i]-1 的值也就会随着改变，所以需要用一个临时变量来保存该值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        vector<int> result(2);
        for(int i=0;i<nums.size();i++){
            while(nums[i]!=i+1 && nums[i]!=nums[nums[i]-1]){
                int j=nums[i]-1;
                int t=nums[i];
                nums[i]=nums[j];
                nums[j]=t;
            }
        }
        for(int i=0;i<nums.size();i++){
            if(nums[i]!=i+1){
                result[0]=nums[i];
                result[1]=i+1;
                break;
            }
        }
        return result;
    }
};

另外，还可以使用 map 来存储每一个元素以及它出现的个数，这样也可以以 O(n)的时间复杂度找到答案，但是空间占用的就会多一些。

最后，在 solution 中看到了一种更有意思的解法，直接使用异或运算，如下所示。

思路是：

  • 首先，将 nums 数组中所有的数进行异或，然后将结果和 1 到 n 再次进行异或，得到的结果一定是重复的数字和缺少的数字异或的结果（因为两个相同的数字异或的结果会是 0）。
  • 然后，通过位运算找到从右往左数第一个非 0 的位。由异或运算的性质可知，两个数异或结果中不一样的位为 1，所以异或结果中任意一个为 1 的位都代表被异或的两个数字中该位不相等。所以，只要找到一个非 0 位，就能把两个数字（重复的和缺少的）给分开了。
  • 继续像之前一样进行异或（nums 数组和从 1 到 n），但是要分成两拨，一波是刚刚找到的那位为 0 的，另一波是为 1 的。分为两组后，这两个数字都是每一组中唯一不重复的数字，所以在异或结束以后，异或的结果就是这两个数字了。
  • 最后判断一下哪一个是重复的数字，哪一个是异或的数字就可以了。

需要注意的是，代码中int rightmostbit=xorall&~(xorall-1);使用的方法十分巧妙，首先，它计算 xorall-1，得到的结果是将 xorall 中从右往左数第一个 1 变成 0，而将这个 0 后的数字变成 1，而第一个 1 左边的数字保持不变。接着，它将这个数字取反（~(xorall-1)），得到的结果是第一个 1 之前的所有数字变成原来数字的相反数，而第一个 1 及其右边的数字变成和原来一样的值（全部为 0）。最后，将 xorall 和得到的新值求且，就可以得到第一个 1 前面的数字全部为 0，而后面的数字也全部为 0 的结果了。

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
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        vector<int> result(2);
        int xorall=0,xor0=0,xor1=0;
        for(int num:nums) xorall^=num;
        for(int i=1;i<=nums.size();i++) xorall^=i;
        int rightmostbit=xorall&~(xorall-1);
        for(int num:nums){
            if((num&rightmostbit)==0) xor0^=num;
            else xor1^=num;
        }
        for(int i=1;i<=nums.size();i++){
            if((i&rightmostbit)==0) xor0^=i;
            else xor1^=i;
        }
        for(int num:nums){
            if(num==xor0){
                result[0]=xor0;
                result[1]=xor1;
                return result;
            }
        }
        result[0]=xor1;
        result[1]=xor0;
        return result;
    }
};