给定一个含 n 个正整数的非空列表 nums ,其中 nums[i] 在区间 [1, n] 内。请找出所有在 [1, n] 范围内但没有出现在 nums 中的数字,并以列表的形式返回结果。
注意:时间复杂度不能超过 O(n)
。
例如:
给定一个列表:[4, 3, 2, 7, 8, 2, 3, 1],返回结果:[5, 6]
给定一个列表:[1, 1],返回结果:[2]
in
判断当前元素是否在 tmp_set 中,如果不在则添加到 res因为题目中限制了 时间复杂度 不得高于
O(n)
,如果上面用in
判断是否在列表 nums 中,list下查找元素的时间复杂度为O(n)
,那么最终时间复杂度将是O(n^2)
;而用
in
判断是否在集合 tmp_set 中,set下查找元素的时间复杂度为O(1)
,那么最终时间复杂度是O(n)
。
def findDisappearedNumbers(nums): res = [] tmp_set = set(nums) for i in range(1, len(nums) + 1): if i not in tmp_set: res.append(i) return res
上面解题方法中,因为我们使用了
set集合
,最终空间复杂度是O(n)
,如果在不考虑返回列表的空间复杂度情况下,有没有方法能够把空间复杂度优化为O(1)
呢?接下来的方法,时间复杂度是
O(n)
,空间复杂度是O(1)
。
说明:
举个例子,最初 nums=[4, 3, 2, 7, 8, 2, 3, 1],如果当前元素为 4 ,那么就把nums中第 4 个元素处理为负数,即 nums=[4, 3, 2, -7, 8, 2, 3, 1]
以此类推,最终 nums=[-4, -3, -2, -7, 8, 2, -3, -1],可以看到 第 5 个元素和 第 6 个元素 都是大于 0 的,那么就说明 5 和 6 都是 所有在 [1, n] 范围内但没有出现在 nums 中的数字。
所以最终得到返回结果:[5, 6]
def findDisappearedNumbers(nums): for i in range(len(nums)): index = abs(nums[i]) - 1 nums[index] = -abs(nums[index]) res = [i + 1 for i, num in enumerate(nums) if num > 0] return res