题目描述
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.
你的算法要求时间复杂度O(n)并且空间复杂度为常量。
思路分析
时间复杂度O(n)，排序是肯定不行了。空间复杂度要求常量，所以只能把额外的空间用作交换。结合题目要求，需要找缺少的最小的整数，假如有10个数，那么这个缺少的最小整数必然在1-11之间。（11表示10个数是1-10连续的，反证法可得，如果缺少的最小整数大于11，那么说明前面11个必然是连续的，而数组最多只有10个数，矛盾）
因此，由于时间复杂度要求O(n)可以想到根据桶排序的思想，由于题目要求所以排序结果必然可以放在原数组中，因为本题的目的不在于排序，所以可以在桶排序的思想上进行变种，直接利用原数组，空间复杂度O(1)。
使用交换，让每个数组下标对应数字，例如例二的[3,4,-1,1]，可以用数组下标0对应数字1，数组下标1对应数字2...则交换后的数组应该为[1,-1,3,4]。然后再遍历一次排序好的数组，找到第一个下标和内容不符的数字，就是结果。
想明白以上过程剩下的实现问题就很简单了，遍历数组，如果当前桶位置的数字与下标不符，例如nums[0]与数字3不符，则交换nums[0]与nums[3 - 1]，当然在交换前要判断3是否超过数组上下界。例外，需要注意[2,2]的情况，既有数字重复，这种情况下目标位置其实已经匹配好了，如果再交换将会无限循环下去，所以要判断下nums[cur]与nums[i]是否相等。
代码实现
public class Solution {
/**
* 157 / 157 test cases passed.
* Status: Accepted
* Runtime: 14 ms
*
* @param nums
* @return
*/
public int firstMissingPositive(int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
// swap nums[i] with nums[nums[i] - 1]
int cur = nums[i] - 1;
if (cur >= 0 && cur < nums.length && nums[cur] != nums[i]) {
int temp = nums[i];
nums[i] = nums[cur];
nums[cur] = temp;
// 交换完以后的数字有可能还要再交换，所以i--，该位置再判断一次
i--;
}
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return nums.length + 1;
}
}
