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;
}
};