【剑指offer】面试题53

问题描述

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

 

示例 1:

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

分析

有序数组，优先考虑二分

分为左右两部分，左侧，nums[i]==i，右侧不等

一直逼近，只到low指向出错的位置

对于[0,1,2,3,...,n-1]这种，查出来low是n-1，实际缺少的是n

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        low =0
        high=len(nums)-1
        
        while(low<high):
            mid=(low+high)//2
            if(nums[mid]==mid):
                low=mid+1
            else:
                high=mid
        # return low如果从0 ~ n - 1都不缺值, 则缺少的是n
        return (low+1 if (low==len(nums)-1 and nums[low]==low) else low)