image.png
AC代码
class Solution {
public int firstMissingPositive(int[] nums) {
if(nums == null || nums.length == 0) {
return 1;
}
for(int i = 0; i < nums.length; i++) {
if(nums[i] <= 0) {
continue;
}
if(nums[i] > nums.length) {
nums[i] = -1;
continue;
}
if(nums[i] == i + 1) {
continue;
}
// >0 && <length
int k = nums[i];
nums[i] = -1;
while(k > 0 && k <= nums.length) {
int tmp = nums[k - 1];
nums[k - 1] = k;
if(k != tmp) {
k = tmp;
}else {
k = -1;
}
}
}
for(int i = 0; i < nums.length; i++) {
if(nums[i] != i + 1) {
return i + 1;
}
}
return nums.length + 1;
}
}
精髓
纯智商题，没什么技巧，想出来就做的出来，想不出来就做不出来。
对当前数字进行重新放置位置，比如[3,5,4,1]，第一个是3，就把他放到3 - 1即第2个位置，并同时把3这个数的位置置为-1，变成[-1, 5, 3,1]，同时tmp值记录下了4，进行同样的处理，4应该放到4 -1即第3个位置。。。如此下去，数组可以变成包含某些正数的数组，第一个下标和数值不一致的就是答案，当然要考虑其他特殊情况，比如全是负数，或者全是同一个数等等。case还是比较多的，容易出错。
