[LeetCode]448. Find All Numbers Disappeared in an Array

题目描述

思路

使用map保存应该出现的数，然后遍历数组，把出现过的数在map中做标记，然后输入map中未被标记的数

代码

class Solution { public: vector<int> findDisappearedNumbers(vector<int>& nums) { vector<int> res = {}; unordered_map<int, int> normal; for (int i = 0; i < nums.size(); ++i){ normal[i + 1] = 1; } for (int &p : nums){ normal[p] = 0; } for (auto &p : normal){ if (p.second){ res.push_back(p.first); } } return res; } };

思路 空间复杂度O(1)

对出现过的数标记为负，在对应位置上数字为正，则该数未出现，输出对应位置

代码

class Solution { public: vector<int> findDisappearedNumbers(vector<int>& nums) { vector<int> res = {}; for (int i = 0; i < nums.size(); ++i){ int m = abs(nums[i]) - 1; nums[m] = nums[m] > 0 ? -nums[m] : nums[m]; } for (int i = 0; i < nums.size(); ++i) { if (nums[i] > 0) { res.push_back(i + 1); } } return res; } };