Ex53-II 0~n-1中缺失的数字

题目描述

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

解题思路

用二分查找，唯一加了一点的地方就是，判断一下之前的那个元素是不是缺失的元素。

代码

class Solution {
 public:
  int missingNumber(std::vector<int>& nums) {
    unsigned low = 0, high = nums.size() - 1;
    while (low <= high) {
      unsigned mid = (low + high) / 2;
      if (mid != nums[mid]) {
        if (mid == 0 || nums[mid - 1] == mid - 1) return mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    return nums.size();
  }
};

结果

执行结果：通过

执行用时：40 ms, 在所有 C++ 提交中击败了59.54%的用户

内存消耗：17.1 MB, 在所有 C++ 提交中击败了31.30%的用户