《剑指offer》刷题系列——（十一）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

思路

因为0~n-1这些数字在数组中是排序的，因此数组中开始的一些数字与它们的下标相同，也就是说，0在下标为0的位置，1在下标为1的位置。

如果不在数组中的某个数字为m，那么所有比m小的数字都与它们的下标相同，但是比m大的数字都比它们的下标大1。我们发现m正好是数组中第一个数值与下标不等的下标。

本题的思路与在排序数组中查找数字相似。

解法

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        left, right = 0, len(nums)-1

        if len(nums) == 0:
            return 0

        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == mid:
                left = mid + 1
            else:
                right = mid - 1

        return left
           

复杂度分析

使用二分法查找，时间复杂度为O(logN)

空间复杂度为O(1)