题目来源
这道题应该算是做过很多次了吧，基本上每次面试都得问一下。
然后刚刚写代码还是写了一会才写出来。
主要思想就是把相应的位置放上相应的数值。其实相当于利用原有空间来做哈希。
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
auto n = nums.size();
vector<int> res;
for (auto i=0; i<n; i++) {
if (nums[i] != i+1 && nums[nums[i]-1] != nums[i]) {
swap(nums[i], nums[nums[i]-1]);
i--;
}
}
for (auto i=0; i<n; i++)
if (nums[i] != i+1)
res.push_back(i+1);
return res;
}
};
我以为这样已经是最好的方法了，没想到还能稍微优化一下。
完全只要遍历两遍，一点都不多。
就是第一次遍历的时候把每个位置里对应数值的位置改为负数。
然后第二遍判断哪些是正数就是消失的数。
代码如下：
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
auto n = nums.size();
vector<int> res;
for (auto i=0; i<n; i++) {
int val = abs(nums[i]) - 1;
if (nums[val] > 0)
nums[val] = -nums[val];
}
for (auto i=0; i<n; i++)
if (nums[i] > 0)
res.push_back(i+1);
return res;
}
};
