【python-面试题53-循环排序】寻找缺失的数

问题描述：

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

示例 1:

输入: [0,1,3]
输出: 2
示例?2:

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

?

循环排序思想：一般可用循环排序解决的问题是：数值一般在一个区间，且是要你在排好序/翻转过的数组中寻找丢失的/重复的/最小的元素。如果当前元素不是在其应该的位置上，则交换该元素和在其应该位置上的元素，直到所有元素都在其应该在的位置上。

接下来解决这一题：由于数组是递增排序的，所以就更简单了。

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

注意，可能返回的是最后一个元素。

结果：

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!