LeetCode简单题之找到所有数组中消失的数字

题目

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
示例 1：
输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]
示例 2：
输入：nums = [1,1]
输出：[2]
提示：
n == nums.length
1 <= n <= 10^5
1 <= nums[i] <= n
进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
来源：力扣（LeetCode）

解题思路

  题目要求查找缺失的数字，首先可以准备一个完整的序列然后逐一对比序列中的值是否在nums中，如果不在则当前值便是缺失的值。这样做的时间复杂度的量级便跑到了O(n^2)，所以需要先哈希一下原数组。

class Solution:def findDisappearedNumbers(self, nums: List[int]) -> List[int]:n=set(nums)temp=[]for i in range(1,len(nums)+1):if i not in n:temp.append(i)return temp

  另外题目给出了进阶的建议，原地完成算法。想要原地空间就必须充分挖掘数组中的元素和下标的关系，在这个题目中，如果我们正常访问能访问到所有的元素，而我们以元素为下标访问数组则会有重复访问的和不能访问到的元素，如果以颠倒元素值和下标为映射关系如何标记已经访问过的元素呢？再开辟一个数组显然不符合要求，直接访问并修改元素值以用来标记又会影响后续的访问。现在似乎需要这样的一个函数；当访问前面元素的时候更改掉以当前元素为下标的元素的值，当访问到被更改的元素的时候，能够还原它原来的值以便找到真正的映射下标，也就是一个函数两次作用于同一个数值是要能回到最初的状态的，这样的函数有求倒数，添负号，加一个足够大的数然后再减去这个数，乘以一个足够大的数然后再除以这个数…；求这个题不能用倒数，因为遇到1会有一些问题。由于这个题目最大值有上限，我们就利用加一个足够大的数。

class Solution:def findDisappearedNumbers(self, nums: List[int]) -> List[int]:n=len(nums)+1  #设置足够大的数for i in nums:  #对应的映射规则if i<n:if nums[i-1]<n:nums[i-1]+=nelse:if nums[i-1-n]<n:nums[i-1-n]+=ntemp=[]for i in range(len(nums)):if nums[i]<=len(nums):temp.append(i+1)return temp

总结

以上是生活随笔为你收集整理的LeetCode简单题之找到所有数组中消失的数字的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。