Description
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
Swap, time O(n), space O(1)
对于给定的nums[]，它应该由[1, n]组成，那么将nums排序之后第一个缺少的元素即为所求。对于这种元素唯一且都在n以内的题目，很自然会想到不需要额外数组辅助，直接在原数组上做swap操作，将元素换到其应该在的位置即可。
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length; // nums should be [1, n]
for (int i = 0; i < n; ++i) {
while (nums[i] != i + 1 && nums[i] > 0 && nums[i] <= n
&& nums[i] != nums[nums[i] - 1]) {
swap(nums, i, nums[i] - 1);
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
public void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
