每日题解:LeetCode 41. 缺失的第一个正数

Author Avatar
清水雅然君 06月 27,2020

题目地址

题目描述

给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。

示例 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
那么我们就可以

  1. 用hashSet维护nums中,大于0的数
  2. 从1遍历到 nums.length,查找nums的数字是否出现在[1,N-1)中,出现就返回
  3. 如果在[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. 数组中重复的数据