题目

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

注意:有序用二分,严禁遍历

示例

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

代码

  • 二分
//对于有序的数组, 都应该想到用二分法搜索
class Solution {
    public int missingNumber(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 数组下标是从0开始连续的向n增长,若相等范围区域继续向右靠
            if (nums[mid] == mid) {
                left = mid + 1;
            }else {
                right = mid - 1;    // 不相等范围区域向左靠拢
            }
        }
        return left;
    }
}

代码分析:如果nums[mid] == mid说明在下标mid之前没有缺失数字。

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;
    }
};

注意:当所有数都满足nums[i] == i时,表示缺失的是 nn。

本文题目que-shi-de-shu-zi-lcof

0~n-1中缺失的数字