HackerHeap

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Note:

Your algorithm should run in O(n) time and uses constant extra space.

Solution 1:

class Solution {
    public int firstMissingPositive(int[] nums) {
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0 && nums[i]!= i+1){
                if(nums[i]>nums.length){
                    continue;
                }else{
                    int temp =nums[nums[i]-1];
                    nums[nums[i]-1] = nums[i];
                    nums[i] = temp;
                }
            }
        }
        
        int retVal = -1;
        int[] temp = new int[nums.length];
        int j = 0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0){
                if(nums[i]>nums.length) continue;
                
                temp[nums[i]-1] = nums[i];
            }
        }
        
        int k = 0;
            
            while(k<temp.length){
                if(temp[k] != k+1){
                        retVal = k+1;
                    break;
                }
                    k++;
            }
        
        if(retVal == -1) return temp.length+1;
        
        return retVal;
    }
}