Given an unsorted integer array nums, find the smallest missing positive integer.
Example 1:
Input: nums = [1,2,0]
Output: 3
Example 2:
Input: nums = [3,4,-1,1]
Output: 2
Example 3:
Input: nums = [7,8,9,11,12]
Output: 1
Constraints:
0 <= nums.length <= 300
-231 <= nums[i] <= 231 - 1
Follow up: Could you implement an algorithm that runs in O(n) time and uses constant extra space?
Solution:
class Solution {
public int firstMissingPositive(int[] nums) {
if(nums.length==0) return 1;
int lastPositiveindex=partition(nums)+1;
for(int i=0;i<lastPositiveindex;i++){
int k=Math.abs(nums[i]);
if(k<=lastPositiveindex)
nums[k-1]=(nums[k-1]<0)?nums[k-1]:-nums[k-1];
}
for(int i=0;i<lastPositiveindex;i++){
if(nums[i]>0){
return i+1;
}
}
return lastPositiveindex+1;
}
public int partition(int[] nums)
{
int j=-1;
for(int i=0;i<nums.length;i++){
if(nums[i]>0){
j++;
int temp = nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
return j;
}
}