消失的数字
题目描述
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
注意：本题相对书上原题稍作改动
示例 1：
输入：[3,0,1] 输出：2
示例 2：
输入：[9,6,4,2,3,5,7,0,1] 输出：8
解法一：使用下标标记
class Solution {
public:
int missingNumber(vector<int>& nums) {
int len = nums.size();
const int MAX_INT = numeric_limits<int>::max();
for(int i=0;i<len;i++){
int n = nums[i];
if(n < 0){
n += MAX_INT;
}
if(n < len && nums[n] >= 0){
nums[n] -= MAX_INT;
}
}
for(int i=0;i<len;i++){
if(nums[i] >= 0){
return i;
}
}
return len;
}
};
解法二：异或
因为不存在重复的数字，而且范围在 [0,n] 之间。对于出现过的数，下标 i 和这个数本身异或之后会清零。
class Solution {
public:
int missingNumber(vector<int>& nums) {
int x = nums.size();
for(int i=0;i<nums.size();i++){
x ^= i ^ nums[i];
}
return x;
}
};