Simple yet best solution in C++, critically commented


  • 1
    class Solution {
    public:
    	//a value of nums[i] should be placed in position nums[i]-1, 
        //using while instead of if in case of the latter are exchanged to 
        //the traversed positions;
        int firstMissingPositive(vector<int>& nums) 
        {
            int size = nums.size();
            for(int i = 0; i < size; ++i)
                while(nums[i]>0 && nums[i]<=size && nums[nums[i]-1]!=nums[i])
                    swap(nums[nums[i]-1], nums[i]);
            for(int i = 0; i < size; ++i)
                if(nums[i] != i+1)
                    return i+1;
            return size+1;
        }
    };

  • 0
    D
    int firstMissingPositive(vector<int>& nums) {
            int n = nums.size();
            for(int i = 0; i < n; ){
                if(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
                    swap(nums[nums[i] - 1], nums[i]);
                else
                    i ++;
            }
            for(int i = 0; i < n; i ++){
                if(nums[i] != i + 1)
                    return i + 1;
            }
            return n + 1;
        }
    

    Using if, instead of while


Log in to reply
 

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