LeetCode448 Find All Numbers Disappeared in an Array

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

样例

1
2
3
4
5
Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

思路

给出一个长度为n的数组,数组元素大小也在[1,n]内,有些数字出现1次,有些出现2次,问哪些数字没出现过。

显然,我们可以开个辅助数组标记哪些数字出现过,然后遍历辅助数组即可找到没出现过的。

但是,不开额外的数组该怎么做呢?那么就必须得充分利用原数组nums!

因此,nums身兼二职,在不破坏原数组信息的情况下,还要肩负起辅助数组的重任!

为了记录信息,不改变nums的值是不可能的,所以我们必须找到一个记录信息的方式,使得要用到nums原值的时候可以很方便恢复回来。一个直观的想法是取负,比如 i 这个数字出现过,则把nums[i]取负(多次出现只取负一次)。因此,想得到nums[i]的原值只需取个绝对值即可,想要知道数字 i 出现过没有只需判断nums[i]是否小于0。

代码

开O(n)的辅助数组:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<bool> exist(nums.size() + 5, false);
for (int i = 0; i < nums.size(); ++i) {
exist[nums[i]] = true;
}
vector<int> ans;
for (int i = 1; i <= nums.size(); ++i) {
if (!exist[i]) ans.push_back(i);
}
return ans;
}
};

不开额外的空间:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<int> ans;
int size = nums.size();
for (int i = 0; i < size; ++i) {
int index = abs(nums[i]) - 1;
if (nums[index] > 0) nums[index] *= -1;
}
for (int i = 0; i < size; ++i) {
if (nums[i] > 0) ans.push_back(i + 1);
}
return ans;
}
};
分享到 评论