Simple Java Solution in O(n)


  • 0
    A
    public class Solution {
        public int firstMissingPositive(int[] nums) {
            if (nums == null || nums.length == 0){
                return 1;
            }
            int temp = Integer.MAX_VALUE;
            for (int i = 0; i < nums.length; i++){
                if (nums[i] <= 0 || (nums[i] - 1) > nums.length){
                    continue;
                }
                else {
                    if (nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]){
                        temp = nums[nums[i] - 1];
                        nums[nums[i] - 1] = nums[i];
                        while (temp > 0 && temp < nums.length){
                            int temp1 = nums[temp - 1];
                            if (temp == temp1){
                                break;
                            }
                            nums[temp - 1] = temp;
                            temp = temp1;
                        }
                    }
                }
                
            }
            int i = 0;
            for (; i < nums.length; i++){
                if (i+1 != nums[i]){
                    return i+1;
                }
            }
            return i+1;
        }
    }

Log in to reply
 

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