当前位置 博文首页 > ervy的博客：leetcode 41. 缺失的第一个正数【原地哈希】
这个题目难点在于要求的时间复杂度O(n)和空间复杂度O(1)，因此只能在原数组上进行操作。
将数组中的数字放置在与之数值相对应的数组下标中。如将数字1放置在下标为0的位置中，将数字5放置在下标为4的位置中…
题目要求仅寻找正整数，因此从1开始遍历。数组中的数字可能比数组长度要大，此时数组长度中一定存在无法与下标对应的数字，那么这个下标遍为需要返回的结果，而超出数组长度的数值可以不用处理。
class Solution {
public int firstMissingPositive(int[] nums) {
int len = nums.length;
for(int i=0; i<len; i++){
while(nums[i] >0 && nums[i]<=len && nums[nums[i]-1]!=nums[i]){
swap(nums, nums[i]-1, i);
}
}
for(int i=0; i<len; i++){
if(nums[i] != i+1){
return i+1;
}
}
return len+1;
}
public void swap(int[] nums, int a, int b){
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}
