C++ solution. O(n) time and O(1) space. just put nunber n at position nums[n-1];


  • 0
    1
    class Solution {
    public:
        vector<int> findDisappearedNumbers(vector<int>& nums) {
            vector<int> result;
            if(nums.empty())
               return result;
            for(int i=0;i<nums.size();++i){
                while(nums[i]!=i+1){
                    int tmp = nums[i];
                    if(nums[tmp-1]==tmp)
                       break;
                    nums[i]=nums[tmp-1];
                    nums[tmp-1]=tmp;
                }
            }
            for(int i=0;i<nums.size();++i)
                if(nums[i]!=i+1)
                   result.push_back(i+1);
            return result;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.