剑指Offer 53- 0~n-1中缺失的数字 - Python

tech2024-12-03  5

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

示例 1:

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

示例 2:

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

限制:1 <= 数组长度 <= 10000


根据题意可知,数字中所有的数字都在[0, n-1]内。因此,首先构建数组包含0~n,然后遍历数组找到那个不在给定数组中的数字即可。

class Solution: def missingNumber(self, nums: List[int]) -> int: if nums == []: return 0 arr = [i for i in range(len(nums) + 1)] for n in arr: if n not in nums: return n return 0

或者是直接遍历原数组,判断数组中的数字和它在数组中索引之间的关系:

如果数字和索引相等,继续往后判断如果数字和索引不等,那么当前索引表示的数字就是所求如果遍历完全部的数字都没有满足条件的,说明当前数组是完全有序的,直接返回nums[-1] + 1,即数组表示的序列的下一个数字 class Solution: def missingNumber(self, nums: List[int]) -> int: if nums == []: return 0 for index, key in enumerate(nums): if index != key: return index return nums[-1] + 1
最新回复(0)