力扣第268题-丢失的数字

1. 题目描述

给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1:

输入:nums = [3,0,1]

输出:2

解释:n = 3,因为有 3 个数字,所以所有的数字都在范围 [0,3] 内。2 是丢失的数字,因为它没有出现在 nums 中。

示例 2:

输入:nums = [0,1]

输出:2

解释:n = 2,因为有 2 个数字,所以所有的数字都在范围 [0,2] 内。2 是丢失的数字,因为它没有出现在 nums 中。

示例 3:

输入:nums = [9,6,4,2,3,5,7,0,1]

输出:8

解释:n = 9,因为有 9 个数字,所以所有的数字都在范围 [0,9] 内。8 是丢失的数字,因为它没有出现在 nums 中。

提示:

n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
nums 中的所有数字都 独一无二

2. 解题思路

2.1 方法一:辅助数组

构造一个全为哦,长度为len(nums)的辅助数组,然后遍历整个列表,将元素放到对应的下表下面,最后再遍历一遍辅助数组,看哪个索引的值是0,返回这个索引即可。

代码实现:

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        # 方法一 使用一个辅助数组
        n = len(nums)
        lst = [0] * (n + 1)
        for num in nums:
            lst[num] = 1
        for i in range(len(lst)):
            if lst[i] == 0:
                return i

2.2 方法二:哈希表

构造一个哈希表,键为nums数组的每一个值,value还是索引的每一个值(或者任意赋一个值即可),最后从1~len(nums) + 1遍历吗,没有找到的那个key就是我们的结果。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        # 方法二:哈希表
        hashmap = {}
        for num in nums:
            hashmap[num] = num
        for i in range(len(nums) + 1):
            if hashmap.get(i) is None:
                return i

2.3 方法三:使用in关键字(python)

这个也很简单,遍历从1 – len(nums) + 1的递增数列,依次判断每个值在不在列表中,如果不在那么直接返回这个值即可。

代码演示:

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        # 方法三: 使用python内置的in关键字
        for i in range(len(nums) + 1):
            if i not in nums:
                return i

3. 总结

这道题目相对来说比较简单,有很多种方法,还可以使用排序后再进行遍历的方法,只不过时间复杂度比上述三种时间复杂度高,感兴趣的可以去看力扣题解。