qiaoxu123
12/25/2018 - 12:19 AM

448. Find All Numbers Disappeared in an Array

  • 第一种方法：使用额外空间实现，hash表记录遍历过的值，从而找到（暴力解法，复杂度高，用时长）

Runtime: 124 ms, faster than 45.37%

  • 第二种方法：使用set数组实现，用count计数来找出现次数为0的数

Runtime: 200 ms, faster than 6.42%

  • 第三种方法：参考Discuss，c++排名最高

复杂度也很高。。

test1.cpp
content_copyfile_download
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> array;
        vector<int> hash;
        hash.resize(nums.size()+1);
        
        for(int i = 0;i < nums.size();++i)
            hash[nums[i]]++; 
        for(int i = 1;i <= nums.size();++i)
            if(!hash[i])
                array.push_back(i);
        
        return array;
    }
};
test2.cpp
content_copyfile_download
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> array;
        set<int> temp;
        
        for(int i = 0;i < nums.size();++i)
            temp.insert(nums[i]);
        
        for(int i = 1;i <= nums.size();++i)
            if(!temp.count(i))
                array.push_back(i);
        
        return array;
    }
};
test3.cpp
content_copyfile_download
//参考Discuss写的
//复杂度还是很高  Runtime: 128 ms, faster than 44.12%
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> array;
        
        for(int i = 1;i <= nums.size();++i){
            int index = abs(nums[i-1]) - 1;
            if(nums[index] > 0){
                nums[index] = -nums[index];
            }
        }
        for(int i = 0;i < nums.size();++i){
            if(nums[i] > 0)
                array.push_back(i+1);
        }
        
        return array;
    }
};