Sword finger offer notes: T53 - ii Missing numbers from 0 to n-1

T53 - II. 0～n-1 Missing numbers in

A length of n-1 All numbers in the incremental sort array of are unique , And every number is in the range 0～n-1 within . In scope 0～n-1 Internal n There are and only one number is not in the array , Please find out the number .

Example 1:

Input : [0,1,3]
Output : 2
Example  2:

Input : [0,1,2,3,4,5,6,7,9]
Output : 8

Limit ：

1 <= The length of the array <= 10000

Ideas

Two points , Replacement in place , See if it corresponds to that number

solution 1

class Solution {
    public int missingNumber(int[] nums) {
           int left =0, right =nums.length-1;
           while(left<=right){
           int mid = left+((right-left)>>1);
           if(nums[mid]>mid){
               right = mid-1;
           }else{
               left = mid+1;
           }
        }
        return left;
    }
}

0 ms, In all  Java  Defeated in submission **100.00%** Users of

Memory consumption ：39.1 MB, In all  Java  Defeated in submission **26.28%** Users of

solution 2

class Solution {
    public int missingNumber(int[] nums) {
           int left =0, right =nums.length-1;
           while(left<=right){
           int mid = left+((right-left)>>1);
           if(nums[mid]==mid){
               left = mid+1;
           }else{
               right = mid -1;
           }
        }
        return left;
    }
}

Execution time ：0 ms, In all  Java  Defeated in submission **100.00%** Users of

Memory consumption ：38.9 MB, In all  Java  Defeated in submission **59.84%** Users of

Time complexity ：O(logn)

Spatial complexity ：O(1)