My Java Solution


  • 0
    M

    Notice that, for a n length array, the result must be among (1,2,....,n+1). So set all other values to 0;

    Then in a loop put the value into the correct index. like 1-> index0, 2->index1, n->index(n-1).

    public int firstMissingPositive(int[] nums) {
                for(int i=0;i<nums.length;i++){
                    //set other values to 0
                    if(nums[i]<1 || nums[i]>nums.length){
                        nums[i]=0;
                        continue;
                    }
                    //try to put the value into the correct index
                    if(nums[i] != i+1 && nums[i]!=0){
                        int j= nums[i];
                        //if nums are duplicated, change self to 0, no switch.
                        //keep the correct value in correct index.
                        if(j==nums[j-1]){
                            nums[i]=0;
                            continue;
                        }
                        //put value to the correct index. 
                        //notice that next loop start from the same i.
                        int temp =nums[j-1];
                        nums[j-1] = nums[i];
                        nums[i]=temp;
                        i--;
                    }
                }
                //check the first nums[m]==0, otherwise, it should be nums.length+1
                for(int m=0;m<nums.length;m++){
                    if(nums[m]==0){
                        return m+1;
                    }
                }
                return nums.length+1;
            }

Log in to reply
 

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