Java Accepted Solution in 1ms with Detailed Comments


  • 0
    B
    /*
    solution is very simple, make input nums to be [3,4,-1,1] as example:
    
    1.Create an array the same length as input: [0,0,0,0]
    2.From the start to the end, check if the element is a positive number.
    3.Then change the created array according to step 2.
    4.Check the array.
    
    For example:
    (Step 2) The first element of the input is 3, then
    (Step 3) Change the 3rd element of array from 0 to 1. So the array from [0,0,0,0] to [0,0,1,0]
    
    At the end the array should be: [1,0,1,1]
    
    (Step 4) if there is still 0 left in the array. then the number of that element will be the answer.
    In this case the answer is 2.
    
    PS. There is the case like: [1,2,3,4] where the created array will become [1,1,1,1] at the end. 
    Then we should return length of array plus one, which is 5 here.
    
    */
    
    public class Solution {
        public int firstMissingPositive(int[] nums) {
            int length = nums.length;                   
            
            //return 1 if the input is an empty array
            if(length == 0) return 1;
            
            int[] list = new int[length];
            
            //step 2 and 3: change the array accroding to nums[]
            for(int i=0; i<length; i++){
                //step 2: check if is positive
                if(nums[i]>0 && nums[i]<=length){
                    //step 3: change the array
                    list[nums[i]-1] = 1;
                }
            }
            
            //step 4: check if there is 0 left
            for(int i=0; i<length; i++){
                if(list[i] == 0){
                    //return the number of this 0
                    return i+1;
                }
            }
            
            //case [1,2,3,4,...,length]
            return length+1;
        }
        
    }

Log in to reply
 

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