0-n-1中缺失的数字

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

示例 1:

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

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

限制：
1 <= 数组长度 <= 10000
通过次数74,996提交次数170,733

二分查找方法

• 如果当前的数字的值大于index的值，说明在其左边有缺失的值。

• 如果当前的数字的值等于index的值，说明在其右边可能有缺失的值。

  import java.util.*;
  public class Solution {
      public int solve (int[] a) {
          int n = a.length;
          int l = 0, r = n-1;
          while(l<=r){
              int m = l+(r-l)/2;
              if(a[m] > m){
                  r = m-1;
              }else{
                  l = m+1;                
              }
          }
          return l;
      }
  }

  二分查找方法

• 如果index和数字相同时，那么缺失的数字一定在当前位置的后面

• 如果index和数字不同时（index<数字），那么缺失的数字是定在当前位置的前面

  class Solution{
      public static int missingNumber(int[] nums) {
          int left = 0, right = nums.length - 1, mid = 0;
          while (left <= right) {
              mid = (left + right) / 2;
              if (nums[mid] == mid) left = mid + 1;           //当index和数字相同时，缺少的数字一定在右边
              else right = mid - 1;                           //当index和数字不同时（数字大于index），缺少的数字一定在左边
          }
          return left;
      }
  }

  顺序查找（不好）

class Solution {
    public int missingNumber(int[] nums) {
        if (nums[0] != 0) return 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] > 1) {
                return nums[i] - 1;
            }
        }
        return nums[nums.length-1]+1;
    }
}

赏

谢谢你请我吃糖果

微信