每日题解: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）的归纳

类似题目

442. 数组中重复的数据

清水1024