Python教程

Python编程题28--找到列表中消失的所有数字

本文主要是介绍Python编程题28--找到列表中消失的所有数字,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目

给定一个含 n 个正整数的非空列表 nums ,其中 nums[i] 在区间 [1, n] 内。请找出所有在 [1, n] 范围内但没有出现在 nums 中的数字,并以列表的形式返回结果。

注意:时间复杂度不能超过 O(n)

例如:

给定一个列表:[4, 3, 2, 7, 8, 2, 3, 1],返回结果:[5, 6]

给定一个列表:[1, 1],返回结果:[2]

实现思路1

  • 设置一个列表res,用于存放没有出现在 nums 中的元素
  • 设置一个集合tmp_set,用于存放 nums 中的不重复元素
  • 遍历区间 [1, n]范围内的所有元素,每次用操作符 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)

实现思路2

  • 遍历nums的所有元素,每次把nums在 [1,n] 下标范围内出现过的处理为负数
  • 遍历结束后,nums中大于 0 的所有元素所处的位置,即 下标 + 1 就是所求的在 [1, n] 范围内,但没有出现在 nums 中的数字

说明:

举个例子,最初 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
这篇关于Python编程题28--找到列表中消失的所有数字的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!