算法创作 | 0到n-1中缺失的数字问题解决方法

问题描述一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。示例1:输入：[0,1,3]输出：2示例2：输入：[0,1,2,4]输出：3解决方案左边界i=0，右边界j=len(nums)-1；闭区间[i,j]。当i≤j时开始循环（即当闭区间[i,j]为空时跳出循环；计算中点m=(i+j)//2，其中"//"为向下取整除法；若nums[m]=m，则“右子数组的首位元素”一定在闭区间[m+1,j]中，便执行i=m+1；若nums[m]=m，则“左子数组末位元素”一定在闭区间[i,m−1]中，因此执行j=m−1；跳出时，变量i和j分别指“右子数组的首位元素”“左子数组的末位元素”，返回i。代码清单 1 找0~n-1中缺失的数的代码清单class Solution:def missingNumber(self, nums: List[int]) -> int:i, j = 0, len(nums) - 1while i <= j:m = (i + j) // 2if nums[m] == m: i = m + 1else: j = m - 1return i运行代码

结语首先看到此题，想到的第一种方法便是二分法，当然，此题也有一些其他的办法，只是二分法更加常用，更容易想到，可以根据规则将数组划分为左子数组和右子数组两部分，根据缺失的数字为右子数组的首位元素作为对应的索引，便可得到所缺失的数。实习编辑：李欣容作者：查萌雨 岳进 赵柔稿件来源：深度学习与文旅应用实验室（DLETA）