one loop Java Solution


  • 0
    G

    this way just need loop once:

    public class Solution {
        public int firstMissingPositive(int[] nums) {
            int temp = 0;
            int max = nums.length;//the possible max value
            
            for(int i=0;i<max;){
                //just check next one
                if(nums[i]==i+1){
                    i++;
                }
                else if(nums[i]<=0||nums[i]>max||nums[i]<i+1||nums[i]==nums[nums[i]-1]){
                    //there are four states to drop the value
                    //swap nums[i]和nums[max-1]
                    temp = nums[i];
                    nums[i]=nums[max-1];
                    nums[max-1] = temp;
                    max--;
                }
                else{
                    //swap nums[i]和nums[nums[i]-1]
                    temp = nums[i];
                    nums[i] = nums[temp-1];
                    nums[temp-1] = temp;
                }
            }
            //now max is real max value,so just need return max+1
            return max+1;
        }
    }
    

Log in to reply
 

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