题目描述
一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0到n-1之内。
在范围0到n-1的n个数字中有且只有一个数字不在该数组中,请找出这个数字。
样例
输入:[0,1,2,4]
输出:3
位运算
利用异或运算的性质
我们先定义一个res=0
然后从0
到n
进行连续异或并把结果保存到 res
里面 即 res = 0^1^2^3^...^n
再把res
与数组中每个元素进行连续异或 即 res = res^nums[0]^nums[1]^nums[2]^nums[3]^...^nums[n-1]
在数组中出现的数字 我们保证进行上面的操作过程中都参与了2次 即成对出现 想一想为什么 是不是很简单
最后没有在数组中出现的那个数一定是单身23333 也就是只在上面操作过程中仅参与了1次
所以就找出单身了 悲伤中......
C++ 代码
可以这么写
class Solution {
public:
int getMissingNumber(vector<int>& nums) {
int res=0;
for(int i=0;i<nums.size();i++) res^=i^nums[i];
// for(auto i:nums) res^=i;
return res^nums.size();
}
};
也可以这么写
class Solution {
public:
int getMissingNumber(vector<int>& nums) {
int res=0;
for(int i=0;i<=nums.size();i++) res^=i;
for(auto i:nums) res^=i;
return res;
}
};
求教第一份代码为什么还要进行res ^ nums.size();呢?我位运算不行
厉害啊,这想法