Question
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
Solution 1 -- HashSet
Note the problem is to find first missing integer, ie, if input is [4,5,7,8], we should return 1.
Naive way is to traverse from 1 to length, find whether they are in original input set. Time complexity O(n), space cost O(n).
public class Solution {
public int firstMissingPositive(int[] nums) {
int length = nums.length;
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < length; i++)
set.add(nums[i]);
int result = 1;
for (int i = 1; i <= length; i++) {
if (!set.contains(i)) {
result = i;
break;
} else {
// Should increase here
// Consider input [1]
result++;
}
}
return result;
}
}
Solution 2
Key is to put i on position (i - 1). Time complexity O(n), space cost O(1).
public class Solution {
public int firstMissingPositive(int[] nums) {
int length = nums.length;
// Put i on (i - 1) position
// Consider three conditions: 1. nums[i] <= 0 2. nums[i] > length 3. duplicates
for (int i = 0; i < length; i++) {
int target = nums[i];
if (target != i + 1) {
// nums[i] <= 0 nums[i] > length
if (target <= 0 || target > length)
continue;
// Duplicate
if (nums[target - 1] == target) {
nums[i] = 0;
continue;
}
// Swap target with nums[target - 1]
int tmp = nums[target - 1];
nums[target - 1] = target;
nums[i] = tmp;
// Still need to check nums[i] after swap;
i--;
}
}
int result = length + 1;
// Check
for (int i = 0; i < length; i++) {
if (nums[i] != i + 1) {
result = i + 1;
break;
}
}
return result;
}
}