41. 缺失的第一个正数
题目描述
题解分析
- 利用哈希表的思想,但是不是使用HashMap。
- 使用整个数组作为哈希桶,每个nums[i]的数字作为索引下标,将其置为负数表示该位置有数字。
- 需要注意最后返回的是n+1表示原来数组中包含所有1-n的数字。
方法一:哈希思想
class Solution {
public int firstMissingPositive(int[] nums) {
//模仿哈希表的原理,使用原来的数组实现hash的目的
int n = nums.length;
//首先小于等于0的数都统一设置为n+1,因为题目要求的是第一个缺失的正数,这个整数一定从1开始
for(int i=0; i<n; i++){
if(nums[i] <= 0)
nums[i] = n + 1;
}
//接着,将hash的位置置为相应的负数,实现hash的目的
for(int i=0; i<n; i++){
int num = Math.abs(nums[i]);//注意这里需要使用绝对值,因为后续可能会将位置上的数字指定为负数
if(num <= n){
nums[num - 1] = -Math.abs(nums[num - 1]);//将相应位置置为负数表示这个位置已经有数字了
}
}
//最后,第一个大于0的位置就是最小正数
for(int i=0; i<n; i++){
if(nums[i] > 0){
return i+1;
}
}
return n + 1;//这里需要注意的是返回最大值,能走到这步说明数组中的元素都是从1到n连续的
}
}
方法二:置换法
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
//置换法
for(int i=0; i<n; i++){
while(nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]){//注意这里有一个循环,因为交换位置后的nums[i]有可能也处在1-n之间,需要再次转换
int temp = nums[nums[i] - 1];
nums[nums[i] -1] = nums[i];
nums[i] = temp;
}
}
for(int i=0; i<n; i++){
if(nums[i] != i+1)
return i+1;
}
return n + 1;//这里需要注意的是返回最大值,能走到这步说明数组中的元素都是从1到n连续的
}
}