剑指Offer 53：0～n-1中缺失的数字

2022年2月25日

剑指Offer 53：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

限制：

1 <= 数组长度 <= 10000

问题的核心在于如何以较低的复杂度找出有序数组中缺失的数字。遇到有序数组应考虑二分法以降低时间复杂度，不断以二分法判断缺失数字是在前半部分还是后半部分。代码的实现机理如下：（a）创建left指针和right指针；（b）当left指针小于right指针时不断循环；（c）首先计算mid指针，当mid指针对应的值小于索引值，说明缺失值在前半部分，那么令right指针为mid-1，反之令left指针为mid+1；（d）直到left指针大于right指针，说明找到缺失值，即为left指针的索引。 三、解题代码

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

为以较低复杂度找到有序数组中的缺失值，通过left、right指针和二分法来查找。