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

类型：数组

1. 找到所有数组中消失的数字 💚
https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/

❓ 给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的整型数组，数组中的元素一些出现了两次，另一些只出现一次。找到所有在 [1, n] 范围之间没有出现在数组中的数字。

💡 排序

如果没有重复和空缺的话，排序后应该是一个公差为 1 的等差数列。正是因为重复，造成了某些数字之间差为 0，某些数字之间差大于 1。

排序后，我们找到这些差大于 1 的数字，其中所间隔的数字就是缺少的数字。
```
class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        nums.sort()
        ans = []
        for i in range(len(nums)):
            if (i == 0 and nums[i] > 1) or nums[i] > nums[i - 1] + 1:
                for n in range(nums[i - 1] + 1 if i > 0 else 1, nums[i]):
                    ans.append(n)
        for n in range(nums[-1] + 1, len(nums) + 1):
            ans.append(n)
        return ans
```
时间复杂度：O(n^2)，空间复杂度：O(1)

💡 原地修改 - 代替哈希

这里其实和「剑指 Offer 03. 数组中重复的数字」中用到的是同一种方法。

由于数字范围在 [1, n] 中，我们可以用一个长度为 n 的数组来代替哈希表。而 nums 数组的长度恰好也是 n，我们能否让 nums 充当哈希表呢？

我们遍历 nums，每遇到一个数 x，就让 nums[x - 1] 增加 n（由于会存在多次增加，因此实际上应该是让 nums[(x - 1) % n] 增加 n）。我们再次遍历时，若发现 nums[i] 未大于 n，则说明数字 i + 1 是缺失的。
```
class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for num in nums:
            x = (num - 1) % n
            nums[x] += n

        ret = [i + 1 for i, num in enumerate(nums) if num <= n]
        return ret
```
时间复杂度：O(n)，空间复杂度：O(1)