剑指Offer[53-2]-0~n-1中缺失的数字

题目

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

示例:

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

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

python代码

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            if nums[i]!=i:
                return i
        return len(nums)

上述解法非常常规,根据题意,数组中的每个值应该等于它的索引值,所以直接遍历整个数组,当发现值不等于索引值时,就说明遇到了缺失值,另外要注意:当遍历结束后,仍没有找到缺失值,则说明缺失值为n。

优化

其实优化的方法也很直接,因为数组为有序数组,且题目涉及到找值,一般情况下都可以使用二分查找法,只不过我们这里的目标值变成了当前值的索引值。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        left=0
        right=len(nums)-1
        if nums[-1]==len(nums)-1:
            return len(nums)
        while left<=right:
            mid = (left+right)//2
            if nums[mid]==mid:
                left = mid+1
            else:
                right = mid-1
        return left

发表评论

电子邮件地址不会被公开。