I hope my wrong Solution can help you


  • 1

    Here is my first implementation based on the top voted answer !

    Maybe it seems no difference with the AC code, but my swap function is wrong !

    class Solution {
    public:
        int firstMissingPositive(vector<int>& nums) {
            int len=nums.size();
            
            for(int i=0; i<len; i++){
                if(nums[i]>0 && nums[i]<=len){
                    while(nums[i]!=nums[nums[i]-1])   swap(nums[nums[i]-1], nums[i]);
                }
            }
            
            for(int i=0; i<len; i++){
                if(nums[i]!=i+1)    return i+1;
            }
            return len+1;
        }
    };
    

    It failed for the case : [0,-1,3,1]

    Because we swap 1 and 0 in the final and then nums[i]=0, so the nums[nums[i]-1] will cause the RE

    Based on the wrong case, we change the code like this:

    class Solution {
    public:
        int firstMissingPositive(vector<int>& nums) {
            int len=nums.size();
            
            for(int i=0; i<len; i++){
                while(nums[i]>0 && nums[i]<=len && nums[i]!=nums[nums[i]-1])   
                    swap(nums[nums[i]-1], nums[i]);
            }
            
            for(int i=0; i<len; i++){
                if(nums[i]!=i+1)    return i+1;
            }
            return len+1;
        }
    };

  • 1

    Move all the number to THE correct position in O(N).

    Then just check one by one to find the first missing positive number.

    Here is the code :

    class Solution {
    public:
        int firstMissingPositive(vector<int>& nums) {
            int n=nums.size();
            for(int i=0; i<n; i++){
                /** check the nums[i] is valid and it is not in its right position **/
                while(nums[i]>0 && nums[i]<=n && nums[i]!=nums[nums[i]-1])
                    swap(nums[nums[i]-1], nums[i]);
            }
            
            for(int i=0; i<n; i++){
                if(nums[i]!=i+1)  return i+1;
            }
            
            return n+1;
        }
    };

  • 0
    2

    I think using the while loop is not easy to understand directly ......

    Here are some tricks to use the while loop to swap the wrong-positioned-num-number with the correct number ..

    Here is the AC C++ implementation

    class Solution {
    public:
        int firstMissingPositive(vector<int>& nums) {
            int size_nums = nums.size();
            for(int i = 0; i < size_nums; i++) {
                while(nums[i] > 0 && nums[i] <= size_nums && nums[nums[i]-1] != nums[i]) {
                    swap(nums[nums[i]-1], nums[i]);
                }
            }
            for(int i = 0; i < size_nums; i++) {
                if(nums[i] != (i+1))  return i+1;
            }
            return size_nums+1;
        }
    };

Log in to reply
 

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