o(n)time ,o(1)place C++ solution


  • 0
    H

    //for each number in nums,swap for 3 times at most.
    int firstMissingPositive(vector<int>& nums) {

        int i=0;
        int n=nums.size()-1;
        if(n==-1)return 1;
        if(n==0)return nums[0]==1?2:1;
        while(i<n){
            if(nums[i]-1>n||nums[i]<=0){
                swap(nums[i],nums[n]);
                n--;
            }else{
                if(nums[i]!=i+1){
                    if(nums[i]!=nums[nums[i]-1])
                        swap(nums[i],nums[nums[i]-1]);
                    else{
                       swap(nums[i],nums[n]);
                       n--;
                    }
                }
                else i++;
            }
        }
        if(nums[i]==i+1)return i+2;
        return i+1;
    }

Log in to reply
 

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