[LeetCode]剑指 Offer 53 - II. 0～n-1中缺失的数字

算法标签：哈希 二分

题目简叙

思路

没什么好说的全都只有一个没在，那直接哈希走起来

代码

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        vector<int>arr(nums.size()+1);
        for(auto it:nums)arr[it]++;

        int res=0;

        for(int i=0;i<arr.size();i++)
            if(!arr[i]){
                res = i;
                break;
            }
        return res; 
    }
};

AC记录

观察可得目标值下标不一致的特性
return nums.size();是我错了两下猜的

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        for(int i=0;i<nums.size();i++)if(nums[i]!=i)return i;
        return nums.size();
    }
};

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