这是我参与11月更文挑战的第8天,活动详情查看:2021最后一次更文挑战。
题目描述:
448. 找到所有数组中消失的数字 - 力扣(LeetCode) (leetcode-cn.com)
给你一个含 n 个整数的数组 nums ,其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字,并以数组的形式返回结果。
示例一
输入: nums = [4,3,2,7,8,2,3,1]
输出: [5,6]
复制代码
示例二
输入: nums = [1,1]
输出: [2]
复制代码
提示:
- n == nums.length
- 1 <= n <= 10^5
- 1 <= nums[i] <= n
进阶:
你能在不使用额外空间且时间复杂度为
的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
思路分析
哈希表
我们可以用一个哈希表记录数组 nums
中的数字,由于数字范围均在 [1,n] 中,记录数字后我们再利用哈希表检查 [1,n] 中的每一个数是否出现,从而找到缺失的数字。
但是这解法的空间复杂度是
的。
但我们的进阶要求是优化空间复杂度到
。
那要降低空间复杂度,就是想办法不再额外利用哈希表呗。
主要到我们的数组 nums
的长度也是正好是 n
。
所以我们可以利用原数组来充当哈希表。
那关键点就变成了如何利用 nums
作为辅助数组,来记录每个数字是否出现过。
具体做法如下:
对于第 i
个数字 nums[i]
,我们位置 (nums[i] - 1) % n
的位置增加 n
,这样不会覆盖原数组,因为 (nums[i] - 1) % n = (nums[i] - 1 + n) % n
,这样如果最后遍历完数组,nums[i]
小于等于 n
,就是数组中中消失的数字。
AC代码
class Solution {
fun findDisappearedNumbers(nums: IntArray): List<Int> {
for(i in 0 until nums.size) {
val x = (nums[i] - 1) % nums.size
nums[x] += nums.size
}
val ans = ArrayList<Int>(nums.size)
for(i in 0 until nums.size) {
if(nums[i] <= nums.size) {
ans.add(i+1)
}
}
return ans
}
}
复制代码
总结
这一题解题过程不长,但是如果不理解的话,可能要想一会,建议拿笔在纸上画画,推演一下就很容易理解了。
参考
找到所有数组中消失的数字 - 找到所有数组中消失的数字 - 力扣(LeetCode) (leetcode-cn.com)
ACM金牌题解 | 不额外开辟空间 | 编程熊 - 找到所有数组中消失的数字 - 力扣(LeetCode) (leetcode-cn.com)
近期评论