算法1

(二分法) $O(logn)$

1. 用二分法找到中间位置，然后判断中间位置的数值和中间位置的下标是否相同，如果相同，则在后半部分寻找。
2. 如果不同，判断前一个数值和下标是否相同或者是否为0，如果相同或者为0，则这个为缺失数字，返回即可
3. 如果不是，则在前半部分继续找

Java 代码

class Solution {
    public int getMissingNumber(int[] nums) {
        if(nums==null||nums.length<0){
            return -1;
        }

        int left = 0;
        int len = nums.length;
        int right = len -1;

        while(left<=right){
            int mid = (left+right)>>1;
            if(nums[mid]!=mid){
                if(mid==0||nums[mid-1]==mid-1)
                    return mid;
                right = mid -1;
            }else{
                left = mid +1;
            }
        }

        if(left == len)
            return len;

        return -1;
    }
}

算法2

(求和运算) $O(n)$

1. 将数组中所有的数值加起来为s1
2. 将本来0——n-1的数值加起来为s2
3. 差值就是和最后一个位置的偏移量，用长度减偏移量就是确实数字的位置

Java 代码

class Solution {
    public int getMissingNumber(int[] nums) {
        if(nums==null||nums.length<0){
            return -1;
        }
        int sum1= 0,sum2 = 0;
        int len = nums.length;

        for(int i = 0 ; i < len; i++){
            sum1 += nums[i];
        }
        for(int i = 0 ; i < len; i++){
            sum2 += i;
        }

        return len-(sum1-sum2);
    }
}