1. 题目
2. 读题(需要重点注意的东西)
思路1(哈希set,时间复杂度O(n),空间复杂度O(n)):
用哈希集合存储每个数,然后从1开始遍历一边哈希集合即可。
但是注意: 题目要求用时间复杂度O(n),空间复杂度O(1)
的算法
思路2(用数组模拟哈希set,时间复杂度O(n),空间复杂度O(1)):
用数组模拟哈希set,在遍历的过程中,将数放在它们应该在的位置上,即进行一个排序操作,具体操作如下:
遍历每一个数,将值的范围在1 ~ n
的数放在下标为0 ~ n-1
的位置上;然后再遍历一遍数组,如果nums[i] != i+1
,则返回i+1
;如果遍历完成,则说明排列好的数组是按1 ~ n
排列的,返回n+1
即可。
3. 解法
---------------------------------------------------解法1---------------------------------------------------:
class Solution {
public int firstMissingPositive(int[] nums) {
Set<Integer> hashset = new HashSet<>();
for(int num : nums) hashset.add(num);
int res = 1;
while(hashset.contains(res)) res++;
return res;
}
}
---------------------------------------------------解法2---------------------------------------------------:
class Solution {
public void swap(int[]nums,int a,int b){
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// 遍历每一个数,将每个数放在它的值-1的位置上( 下标为0 ~ n-1 )
// 即将nums[i] = 1放在下标为nums[i] - 1=0的位置上,即nums[nums[i]-1] = nums[i]
for(int i = 0;i < n;i++)
// 负数和0不用管、大于n的数不用管
while(nums[i] > 0 && nums[i] <= n && nums[i] != i + 1 && nums[i] != nums[nums[i] - 1])
swap(nums,i,nums[i]-1);
// 遍历一遍,如果当前位置和它的值不同,则返回i+1,否则返回n+1
for(int i = 0;i < n; i++ )
if(nums[i] != i+1)
return i+1;
return n+1;
}
}
可能存在的问题:
4. 可能有帮助的前置习题
5. 所用到的数据结构与算法思想
6. 总结
掌握用数组模拟哈希set的方法,重点注意数的转换swap操作。