LeetCode 448. 找到所有数组中消失的数字（哈希表）

448. 找到所有数组中消失的数字

思路：方法一，借助额外的0(n)空间sta进行哈希

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n=nums.size();
        vector<int> sta(n,0);
        for(int i=0;i<n;i++){
            sta[nums[i]-1]=1;
        }
        vector<int > v;
        for(int i=0;i<n;i++){
            if(sta[i]!=1) v.push_back(i+1);
        }
        return v;
    }
};

思路：进阶版。方法二，借助数组nums本身的空间进行哈希

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n=nums.size();
        for(int i=0;i<n;i++){
        	//用n+1来标记是否存在该元素。
        	//如果当前元素不为n+1，说明当前的nums[i]还未进行标记处理
            if(nums[i]!=n+1){
            	//获得需要处理的元素，减1是因为下标的范围为0~n-1
                int j=nums[i]-1;
                //进行循环处理
                while(nums[j]!=n+1){
                    int tmp=nums[j]-1;
                    nums[j]=n+1;
                    j=tmp;
                }
            }
        }
        vector<int > v;
        for(int i=0;i<n;i++){
            if(nums[i]!=n+1) v.push_back(i+1);
        }
        return v;
    }
};