每日题解:LeetCode 41. 缺失的第一个正数
题目描述
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
提示：
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
解法
JAVA
hashSet(时间复杂度不符合条件)
public class Solution {
public int firstMissingPositive(int[] nums) {
int len = nums.length;
Set<Integer> hashSet=new HashSet<>();
for (int num : nums) {
if(num>0) {
hashSet.add(num);
}
}
for (int i = 1; i <=len ; i++) {
if(hashSet.contains(i)){
return i;
}
}
return len+1;
}
}
JAVA
数组(正确解法)
public class Solution {
public int firstMissingPositive(int[] nums) {
int len = nums.length;
int temp =0;
for(int i = 0;i<len;++i){
//调整位置
while (nums[i]>0 && nums[i]<= len && nums[i] != nums[nums[i]-1]){
temp = nums[nums[i]-1];
nums[nums[i]-1] =nums[i];
nums[i] =temp;
}
}
for(int i=0;i<len;++i){
if(nums[i] != i+1){
return i+1;
}
}
return len+1;
}
}
解题思路
hashSet
缺失的最小正整数的范围
假设我们需要寻找到得最小正正数为N，可以肯定的一点，N >= 1，由于题目要求其中没有出现的最小的正整数。那么意味着，1 、2、 3、 …… 、n-1 肯定出现在数组里，大于N的数不用考虑，那么就可以得出
nums.length >= n-1 ，即 n >= nums.length+1
比方说，[1,2,3]，数组的长度为3,1，2，3已经出现在数组中，那么答案就是 nums.length+1即4
那么我们就可以
- 用hashSet维护nums中，大于0的数
- 从1遍历到 nums.length，查找nums的数字是否出现在[1,N-1）中，出现就返回
- 如果在[1,N-1中没有出现答案，那就返回 nums.length+1;
int len = nums.length;
Set<Integer> hashSet=new HashSet<>();
for (int num : nums) {
if(num>0) {
hashSet.add(num);
}
}
for (int i = 1; i <=len ; i++) {
if(hashSet.contains(i)){
return i;
}
}
return len+1;
}
交换数组位置
hashSet虽然能解决问题，但是其时间复杂度为线性的，O(n)不符合题意，那么就换一个思路，将数组进行处理，将数值为 i 的数映射到下标为 i - 1 的位置，把 1这个数放到下标为 0 的位置， 2这个数放到下标为 11 的位置，按照这种思路整理一遍数组。当我们遇到第一个遇到的它的值不等于下标的那个数,就是我们的结果了
//将i放到所以 应该放在索引 i-1 的位置上
while (nums[i]>0 && nums[i]<= len && nums[i] != nums[nums[i]-1]){
temp = nums[nums[i]-1];
nums[nums[i]-1] =nums[i];
nums[i] =temp;
}
这里有个地方可读性比较差，nums[nums[i]-1];这里就是获取i-1位置上的值，然后和当前i的值进行互换
，前提条件是在[1, N]的范围内进行互换，互换结束后，遍历寻找答案
//由于i放到了索引 i-1 的位置上，需要索引需要+1
for(int i=0;i<len;++i){
if(nums[i] != i+1){
return i+1;
}
}
也可以尝试解决下面这个问题，解决方法类似，不过这种题目，一般看题目时间和空间复杂度要求，如果没限制使用set就可以了，还有空间要求，就用原地排序数组，如果要求空间O(1)并且不能修改原数组，还得写成二分法！！！可以参考李哥题解原地哈希（哈希函数为：f(nums[i]) = nums[i] - 1）的归纳
类似题目