53. 0~n-1中缺失的数字

题目

https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/

思路

数组已经排序，且唯一，找出缺失的数字，那么遍历一遍，比较索引与当前值，即可知道缺失的数字。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        for i, val in enumerate(nums):
            if i == val:
                continue
            else:
                return i
        return len(nums)

这样算法时间复杂度是O（n)。

看到数组是有序的或者部分有序，那么考虑是否可以用二分查找。只要索引 i== cur_val，那么说明前i个元素是已经严格从小到大依次排序。详见代码

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        # 二分法
        if nums[-1] < len(nums): return len(nums)
        if nums[0] > 0: return 0
        left, right = 0, len(nums) - 1
        while left + 1 < right:
            mid = left + (right - left) // 2
            if nums[mid] == mid:
                # 说明前mid都是依次排序的
                left = mid + 1
            else:
                right = mid
        return left if nums[left] != left else right