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. 排序后二分查找

先说求和的思路，既然要找出序列0~n中存在而在给定数组中不存在元素，那就先对0~n的序列求和，求和之后再减去数组的所有元素和，差值就是missing number，代码如下:

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

这并不是一个好的思路，因为一旦数据量很大，size*（size+1）可能会溢出

下面说说位操作的思路，考虑六种位操作中只有异或操作能够用于这个问题的解答，所谓异或就是”相同则返回0，不同返回1”

根据异或的性质，如果一个序列中某一个数出现了一次而其他的数都出现了两次，那么容易证明所有元素进行异或之后剩下的那个就是只出现了一次的数，所以，我们大致思路如下:

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

当然，我们发现之所以上面的算法要分成两轮循环来做，是因为两次循环条件不一样，正好相差一个值nums.size();正因为此，如果我们将x初始化为nums.size(),就可以one-pass解决问题，避免无用的循环。

优化后的代码如下:

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

最后说说二分查找，首先要排序，这导致该算法最低时间复杂度也是O(nlogn)，所以我们并不会采用这个方法;排序后进行二分查找，对中间元素的值和下标值进行比较，若中间值等于下标值，则说明missing number在右半区，否则在右半区。