c++ 0(N) one space with swap


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

  • 0

    after see the using sigh to store imformation, wo gan bai xia fen!


  • 0

    give a better solution :

        int n=nums.size();
        for(int i=0;i<nums.size();++i)            
        { 
            int t=nums[i]%(n+1)-1;
            nums[t]+=n+1;
        }
        vector<int>ans;
        for(int i=0;i<nums.size();++i)
              if(nums[i]<n+1)
                ans.push_back(i+1);
        return ans;

Log in to reply
 

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