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

题目

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

示例：

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

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

解答 & 代码

原地哈希：数组 nums 中含有 n 个数，且所有数恰好都在区间 [1, n]，那么可以让 nums[i] 的符号代表数字 i + 1 是否出现过，即，如果最终 nums[i] 为负数，则说明数字 i + 1 出现过，否则未出现

  1. class Solution {
  2. public:
  3.     vector<int> findDisappearedNumbers(vector<int>& nums) {
  4.           // 遍历数组，修改（原地的）哈希表
  5.         for(int i = 0; i < nums.size(); ++i)
  6.         {
  7.             int idx = abs(nums[i]) - 1;
  8.             if(nums[idx] > 0)
  9.                 nums[idx] = -nums[idx];
  10.         }
  12.           // 再次遍历数组，如果 nums[i] 是正数，则说明 i + 1 未出现过
  13.         vector<int> answer;
  14.         for(int i = 0; i < nums.size(); ++i)
  15.         {
  16.             if(nums[i] > 0)
  17.                 answer.push_back(i + 1);
  18.         }
  19.         return answer;
  20.     }
  21. };

复杂度分析：设数组 nums 中含有 n 个数

  • 时间复杂度 O(n)
  • 空间复杂度 O(1)

执行结果：

  1. 执行结果：通过
  3. 执行用时：40 ms, 在所有 C++ 提交中击败了 84.56% 的用户
  4. 内存消耗：32.9 MB, 在所有 C++ 提交中击败了 60.27% 的用户