题目描述
题目直达
题目难度——困难
方法一:暴力
虽然题目说你能在 O(N) 时间内只用 O(1) 的空间找到它们吗? 但是也没有限制我们不能用暴力,而且题目也给了nums的长度最多也就30000,那么暴力遍历一遍应该也用不了多少时间。至于空间,需要用到O(N),首先新建一个包含1到N的数组,然后给输入数组填补两个0,让他们长度对其。注意题目没有说输入数组是有序的,所以还需要对nums进行排序。最后再遍历两个数组进行比对,就能找到缺失的答案了。
代码
class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
vector<int> res;
vector<int> tmp(nums.size() + 2);
for(int i = 0; i < nums.size() + 2; i++){
tmp[i] = i + 1;
}
sort(nums.begin(), nums.end());
nums.push_back(0);
nums.push_back(0);
for(int i = 0, j = 0; i < nums.size();){
if(nums[i] != tmp[j]){
res.push_back(tmp[j]);
j++;
}
else if(nums[i] == tmp[j]){
i++;
j++;
}
if(res.size() == 2){
break;
}
}
return res;
}
};
代码优化
class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
vector<int> res;
int tmp[nums.size() + 2];
for(int i = 0; i < nums.size() + 2; i++){
tmp[i] = i + 1;
}
sort(nums.begin(), nums.end());
nums.push_back(0);
nums.push_back(0);
for(int i = 0, j = 0; res.size() != 2; j++){
if(nums[i] != tmp[j]){
res.push_back(tmp[j]);
}
else{ // else it must be the same
i++;
}
}
return res;
}
};
方法二——数学方法
既然缺失两个数A和B,那么输入数组的总和与1到N的总和之间的差一定是缺失的那两个数之和。我们只需要先获得这两个和的差,即A+B=Sum(1,…N)-Sum(nums)。然后用两个指针从从A+B的中间开始往两边走,找到不在nums里的那两个数就是答案。因此需要额外借助一个字典或者集合来存储nums。
代码
class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
vector<int> res;
unordered_map<int, int> table;
for(int i = 0; i < nums.size(); i++){
table[nums[i]] = nums[i];
}
int N = nums.size() + 2;
int diff = (1 + N) * N / 2 - accumulate(nums.begin(), nums.end(), 0);
int left = diff / 2;
int right = diff - left;
while (res.size() != 2){
if(!table.count(left) && !table.count(right)){
res.push_back(left);
res.push_back(right);
}
--left;
++right;
}
return res;
}
};
总结
两种方法都比官方题解中的位运算方法要慢,第一种由于用到了sort,所以时间是O(NlogN),空间是O(N),第二种最坏情况下缺失的数字是1和N,那就要遍历N/2次,所以时间也是O(N)。额外的空间如果使用map来进行查找的话,是O(logN),set也是O(logN),总之第二种方法也是时间和空间都是O(N)。