数据结构与算法

数组 Ⅱ

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

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

示例 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 <= 105
  • 1 <= nums[i] <= n

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

解法 1

算法与数据结构

利用哈希表，遍历一遍数组，记录所有数字出现的次数。最后遍历哈希表，找到未出现的数字即为结果。

参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public:
    vector<int> findDisappearedNumbers(vector<int> &nums) {
        unsigned long long n = nums.size();
        unordered_map<int, int> mp;
        for (const auto &num : nums) {
            mp[num - 1] += 1;
        }

        vector<int> res;
        for (int i = 0; i < n; ++i) {
            if (mp.count(i) == 0) {
                res.push_back(i + 1);
            }
        }

        return res;
    }
};

注：operator[] 在 key 不存在时会默认插入，如果使用 if (mp[i] == 0) 判断，若 i 不存在于 mp，会自动插入 {i: 0}。虽然不影响正确性，但是会导致第二轮循环中 mp 不断膨胀。

复杂度分析
  • 时间复杂度：，循环遍历的复杂度为 ，哈希表插入与查询均为 ；
  • 空间复杂度：，哈希表最多存储 个键值对；

解法 2

算法与数据结构

既然数组内元素的范围是 ，那么可以用原地标记的方法将额外空间压缩到 .

参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public:
    vector<int> findDisappearedNumbers(vector<int> &nums) {
        for (int num : nums) {
            int idx = abs(num) - 1;
            if (nums[idx] > 0) {
                nums[idx] = -nums[idx]; // exist
            }
        }

        vector<int> res;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] > 0) {
                res.push_back(i + 1);
            }
        }

        return res;
    }
};
复杂度分析
  • 时间复杂度：，循环遍历的复杂度为 ，哈希表插入与查询均为 ；
  • 空间复杂度：；