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

题目描述：

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

进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

示例 1：

1
2

输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

示例 2：

1
2

输入：nums = [1,1]
输出：[2]

提示：

• $n == nums.length$
• $1 <= n <= 10^5$
• $1 <= nums[i] <= n$

链接：

https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array

题目分析

  我们需要找到数组中没有出现过的数字，最容易想到的就是使用哈希表记录出现过的数，这样需要空间大小为 $O(n)$ 的哈希表。而进阶要求中说不使用额外空间，那我们就需要思考原数组如何利用。可以知道原数组的大小也是 n，是否可以将原数组当成一个哈希表来使用呢？区间 [1, n] 的各个数字刚好对应数组 [0, n-1] 各个下标。
  遍历数组，对于出现的元素 num 我们就标记 nums[num-1]，我们考虑如何进行标记，因为 nums[num-1] 可能还未被遍历到，需要标记后仍然能使用。一种方法是标记的时候将其作为下一个查找的目标，那样需要在数组中跳跃。另一种就是考虑标记后能够还原成原数字的方法，比如数字的范围是 1~n，那我们可以将其置为相反数，还原的时候取绝对值就可以。
  具体操作就是每次将需要标记的下标计算出来（当前元素的绝对值减一），然后判断其是否未标记（仍然是正数），然后进行标记（置为相反数）。全部标记完毕后，我们就可以遍历数组，对于每个仍是正数的元素，说明其下标加一的那个数不存在数组中，加入结果数组。对于负数的元素我们进行还原（这个操作好像也可以不要，题目不检查是否已经改动了原数组）。这样就达到了进阶的要求。
  PS：这样的算法也是一种原地算法，就是在原数组进行操作的算法。官方题解也是差不多的思路，而进行标记的方法是加上 n，这样也会超过原数字的范围，然后还原的方法是对 n 取余。这样也是一种方法，好处是操作之前不需要先判断是否已经标记，因为再次加 n 也不会造成影响。但是不好的地方在于其实这样是会越界的，题目中 n 的范围可以到 $10^5$，这样最大的标记可以到达 $10^{10}$，这是超过了 int 的范围的，貌似最后的测例并没有这么大，所以官方题解可以通过所有测例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        for(const int& num : nums){
            int index = abs(num) - 1;
            if(nums[index] > 0){
                nums[index] = 0 - nums[index];
            }
        }
        vector<int> result;
        for(int i = 0; i < n; i++){
            if(nums[i] > 0){
                result.push_back(i + 1);
            }
            else{
                nums[i] = 0 - nums[i];
            }
        }
        return result;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是数组的大小。我们对数组进行了两次遍历，一次是进行标记，一次是寻找结果。
  空间复杂度：$O(1)$。我们在原数组进行操作，而结果数组不计入空间复杂度。