LeetCode.448找到所有数组中消失的数字

这是我参与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

进阶：

你能在不使用额外空间且时间复杂度为

O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

思路分析

哈希表

我们可以用一个哈希表记录数组 nums 中的数字，由于数字范围均在 [1,n] 中，记录数字后我们再利用哈希表检查 [1,n] 中的每一个数是否出现，从而找到缺失的数字。

但是这解法的空间复杂度是

O(n) 的。

但我们的进阶要求是优化空间复杂度到

O(1)。

那要降低空间复杂度，就是想办法不再额外利用哈希表呗。

主要到我们的数组 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)