0～n-1中缺失的数字

题目：

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例：

输入: [0,1,3]
输出: 2

限制：

1 <= 数组长度 <= 10000

解题方法：

方法1：

利用数学中等差数列求和公式计算不缺失数据下数组累加和是多少，然后减去数组中所有的元素，剩余数值就是缺失的数据。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n=nums.size();
        long long sum=(0+n)*(n+1)/2;  // Arithmetic sequence summation formula
        for (int i=0;i<n;i++)
        {
            sum-=nums[i];
        }
        return sum;
    }
};

这是我自己做的时候想到的方法，最后速度上击败的人不多，但是内存使用上击败了很多人，感觉结果也还行。

依稀记得有一手异或操作可以找到缺失数据，但是具体怎么用却不记得了，所以就翻了一下leetcode上的解题方法，于是就有了下面两种方法。

方法2：

异或法，主要使用的是异或的两个特点：

a=a^0;
0=a^a;

因为数组下标和数组元素原本应该是一一相等的，但是缺少了一个数据就导致了最终有一个下标和元素最大值是不相等的，考虑到使用异或运算的特性，我们人为的添加一个数n（数组下标），这样，最终异或的结果就是缺少的数：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n=nums.size();
        int missing=n;    //add number n to match array element max number n
        for(int i=0;i<n;i++)
        {
            int temp=i^nums[i];
            missing=missing^temp;
        }
        return missing;
    }
};

方法三：

leetcode上的大佬表示，没有充分利用递增这个条件的方法都不能算是真正理解题目，如何使用递增呢？大佬们说用二分搜索:

当mid==nums[mid]，说明mid左边的数组不缺少数据，应该从mid右边数组搜索，left=mid+1
当mid!=nums[mid]，说明缺失数据的位置在mid左边（包括mid）。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int end=nums.size();
        int start=0;
        while(start<end)
        {
            int mid=(start+end)>>1;
            if(mid<nums[mid])
                end=mid;
            else
                start=mid+1;
        }

        return start;
    }
};

这道题还是很简单的，不过我从简单的做起来，希望后面做的多了，可以自己独立实现一些更复杂的算法题。