LeetCode题目笔记——17.19消失的两个数字

题目描述

题目直达

题目难度——困难

方法一：暴力

  虽然题目说你能在 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)。