Java 1ms Easy to understand


  • 0
    H
    public int firstMissingPositive(int[] nums) {
            if(nums == null || nums.length == 0) return 1;
            int len = nums.length;
            int i = 0, j = len - 1;
            // Re-arrange the nagative numbers to the end of array
            while(i <= j) {
                if(nums[i] <= 0) {
                    while(i <= j && nums[j] <= 0) {
                        j--;
                    }
                    if(i < j) {
                        int temp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = temp;
                        j--;
                    }
                }
                i++;
            }
            
            // Re-arrange the positive numbers to make the number locates at corresponding index
            i = 0;
            len = j + 1;
            while(i < len) {
                if(nums[i] > len || nums[nums[i] - 1] == nums[i]) {
                    i++;
                } else {
                    int temp = nums[i];
                    nums[i] = nums[temp - 1];
                    nums[temp - 1] = temp;
                }
            }
            
            // Check which is the first positive number missing
            i = 0;
            while(i < len) {
                if(nums[i] != i + 1) return i + 1;
                i++;
            }
            
            return len + 1;
        }

Log in to reply
 

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