# 268.Missing Number

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

For example, Given nums = [0, 1, 3] return 2.

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

1. 等差数列求和
2. 位操作中的异或操作
3. 排序后二分查找

/*solution1 32ms accumulate the sequence from 0 to n,
not a good algorithm，when the test case is large，maybe overflow.
*/
class Solution {
public:
int missingNumber(vector<int>& nums) {
return ((nums.size()*(nums.size()+1))>>1)-accumulate(nums.begin(),nums.end(),0);/*parameter 0 is initial value*/
}
};


1. 让序列0~n中每一个元素先进行异或,得x
2. 让数组中每一个元素进行异或，得y
3. 返回x异或y的值

/*solution2 use bit manipulation and the property of XOR 36ms*/
class Solution {
public:
int missingNumber(vector<int>& nums) {
int x=0,y=0,i=0;
for(i=0;i<=nums.size();i++)
x^=i;
for(i=0;i<nums.size();i++)
y^=nums[i];
return x^y;
}
};


/*solution3 one-pass,with bit manipulation 38ms*/
class Solution {
public:
int missingNumber(vector<int>& nums) {
int x=nums.size(),y=0,i=0;
for(i=0;i<nums.size();i++)
x=x^i^nums[i];
return x;
}
};


### 学籍管理系统文档

#### 北邮教务系统评教脚本

Published on September 17, 2017

#### 72.Edit distance

Published on September 17, 2017