题目:

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

分析:

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

最先想到将数组进行排序,再依次判定数和索引是否对应,首次不对应的索引便是缺失的数。不过由于需要对数组进行排序,这样时间复杂度就不会是线性的了。

也可以创建一个集合,将数组中元素添加进集合中,再从0到n对集合进行查询,不在集合内的便是缺失的数。不过这样空间复杂度就不是常数级的了。

我们知道所给的数的序列是从0到n,且只缺失一个数,根据高斯求和公式,可以快速求得0到n这n+1个数的和,再减去序列中的n个数,剩下的便是缺失的数。

还可以利用异或运算(XOR),我们知道对一个数进行两次完全相同的异或运算会得到原来的数,即

a ^ b ^ b = a

a ^ a = 0

根据题目我们知道,未缺失的数,在[0-n]和数组中各出现了一次,而缺失的数只在[0-n]中出现了一次,根据这个条件和异或的特性可以通过一次循环求得缺失数。

假设所给的序列为0,1,3,4,我们可以求得

missing = 4 ^ 0 ^ 0 ^ 1 ^ 1 ^ 2 ^ 3 ^ 3 ^ 4

     = (4 ^ 4) ^ (0 ^ 0) ^ (1 ^ 1) ^ 2 ^ (3 ^ 3)

     = 0 ^ 0 ^ 0 ^ 0 ^ 2

     = 2

程序:

C++

//use math
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();
int res = (+n)*n/;
for(int q:nums)
res -= q;
return res;
}
};
//use xor
class Solution {
public:
int missingNumber(vector<int>& nums) {
int res = nums.size();
for(int i = ; i < nums.size(); ++i){
res = res ^ i ^ nums[i];
}
return res;
}
};

Java

class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
int res = (1+n)*n/2;
for(int q:nums)
res -= q;
return res;
}
}
class Solution {
public int missingNumber(int[] nums) {
int res = nums.length;
for(int i = 0; i < nums.length; ++i){
res = res ^ i ^ nums[i];
}
return res;
}
}
05-11 20:25