Java AC O(n) Solution


  • 0
    A
    public int firstMissingPositive(final int[] nums) {
            int i = 0;
            while (i < nums.length) {
                int num = nums[i];
                if (i != num-1 && num >= 1 && num <= nums.length && num != nums[num-1]) {
                    swap(nums, i, num-1);
                } else {
                    i++;
                }
            }
    
            for (i = 0; i < nums.length; i++) {
                int num = nums[i];
                if (i != num-1) {
                    return i+1;
                }
            }
    
            return nums.length + 1;
        }
    
        private void swap(final int[] nums, final int i, final int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    

Log in to reply
 

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