算法1

思路：哈希表做法，我更喜欢这个解法吧，很简单。首先把1到n全部存到哈希表里，然后把哈希表中出现过的数组里面的数去除，剩下的就是缺失的数

C++ 代码

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        unordered_set<int> S;//定义一个哈希表，
        for(int i=0;i<=nums.size();i++)S.insert(i);//把数放到哈希表里面

        for(auto x:nums) S.erase(x);//在长度为n的哈希表中删除nums中的元素，剩下来的就是忽略掉的元素
         return *S.begin();
    }  
};

算法2

思路：二分做法，其实也蛮简单的，如果和中间值不一样，说明缺失的就是那个数

C++ 代码

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        if(nums.empty())return 0;
        int l=0,r=nums.size()-1;
        while(l<r)
        {
            int mid=l+r>>1;
            if(nums[mid]!=mid)r=mid;//核心
            else l=mid+1;
        }
        if(nums[r]==r)r++;
        return r;
    }
};