[Leetcode 448] Find All Numbers Disappeared in an Array

作者 Shilei Tian 日期 2016-12-26
[Leetcode 448] Find All Numbers Disappeared in an Array

题目要求

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.

Example

Input:

[4,3,2,7,8,2,3,1]

Output:

[5,6]

解题思路

题目的要求很简单,给定一个数组,里面的元素都是在 [1,n] 范围内,其中 n 是数组的大小。这些元素要么出现一次,要么出现两次。题目希望我们的空间复杂度为 O(1),这就要求我们不能开标记数组。

那么我们很容易想到一个耿直的做法,先将数组元素排序,设置一个变量表示下一个要对比的元素 next。然后从第一个元素开始,每次检查 next 与当前元素是否相等,如果相等,则将 next 增加一个后进行继续循环;如果不相等,那么就说明,从 next 到当前元素之间的所有元素都是缺失的,那么我们需要将这一范围内的所有元素添加到需要返回的结果当中。这里面需要注意会重复的元素即可。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<int> ret;
sort(nums.begin(), nums.end());
int next = 1;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] != next) {
while (next < nums[i]) {
ret.push_back(next++);
}
}
if (i < nums.size() - 1 && nums[i] == nums[i + 1]) {
++i;
}
++next;
}
while (next <= nums.size()) {
ret.push_back(next++);
}
return ret;
}
};

上述代码的时间复杂度是 O(nlog),主要是排序这一步占用时间。那么还有没有更好的思路来解决这个问题呢?通过查看 Top Solutions,找到了一个时间复杂度为 O(n) 的算法,非常巧妙,先上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<int> ret;
for (auto num : nums) {
int index = abs(num) - 1;
if (nums[index] > 0) {
nums[index] = -nums[index];
}
}
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] > 0) {
ret.push_back(i + 1);
}
}
return ret;
}
};

算法的第一步,将数组中每个元素指向的那个元素设置为它的负数。比如,我们当前正在检查的元素值为 4,那么我们就将数组第四个位置(对应下标应该为 3)设置为负数,当然如果它本身就是负数(这种情况对应的是该元素已经出现过一次了),就不需要处理。这一步执行完了,我们就将遇到过的元素都标记为了负数。

第二步就是从头遍历这些元素,如果哪个元素的指还是正数,那么就说明它这个下标 +1 对应的那个数字没有出现。这就是关键的地方。

用这种方式,我们进行两次遍历就可以得到结果。

总结

这道题目非常有意思,高效的解充分地运用了题目所给的每一个条件。耿直的做法根本没用数组里面的元素都是在 [1,n] 范围内这个条件。