Leetcode41. 缺失的第一个正数

题目描述

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

**进阶：**你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？

示例 1：

1
2
输入：nums = [1,2,0]
输出：3

示例 2：

1
2
输入：nums = [3,4,-1,1]
输出：2

示例 3：

1
2
输入：nums = [7,8,9,11,12]
输出：1

提示：

  • 0≤nums.length≤3000 \leq nums.length \leq 300
  • −231≤nums[i]≤231−1-2^{31} \leq nums[i] \leq 2^{31} - 1

解题思路

这道题如果不规定时间复杂度和空间复杂度的话就是简单题。

方法一：哈希表法

如果抛开时间复杂度和空间复杂度的限制，我们自然想到可以用哈希表来记录数组中出现的元素，然后从1开始遍历[1,len]之间的正整数，如果哪一个没有被记录，那就是第一个缺失的元素。如果遍历结束都没返回，说明前len个整数都没有缺失，直接返回len+1。

示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int firstMissingPositive(vector<int>& nums)
{
    if(nums.empty()) return -1;
    unordered_map<int,bool>mp;

    for(int i=0;i<nums.size();++i)
    {
        if(mp[nums[i]]) continue;
        mp[nums[i]]=true;
    }

    for(int i=1;i<=nums.size();++i)
    {
        if(!mp[i]) return i;
    }
    return nums.size()+1;
}

时间复杂度为：O(n)O(n)

空间复杂度为：O(n)O(n)

方法二：原地哈希法

如果要达到规定的时间复杂度和空间复杂度，那么我们就要自己原地实现哈希算法。

容易发现的是，要找的数一定是在区间[1,len+1]（len是数组的长度）中。因为，如果在数组中有个元素比len大，那么在[1,len]中一定存在确实的数。不然的话，前len个数都存在，就返回len+1。

由于，要找的数一定是在区间[1,len+1]中，所以我们可以将原始的数组当成哈希表。在原地实现哈希算法。这个哈希算法也比较简单，**将k这个数重新放在下标为k-1的位置。**也就是说，只要数i+1存在，原始数组的下标i处就放置数i+1。这样的话，下标[0,len-1]的数组就映射为了[1,len]，最后的时候只要遍历一遍数组，如果对应规则不对，就返回映射过去的数；如果遍历结束还没返回答案，就返回len+1。

在实现哈希函数的时候，用while循环去实现，并且要保证数都在特定范围之内，超出范围的直接舍弃就好。

具体细节见示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int firstMissingPositive(vector<int>& nums)
{
    if(nums.empty()) return -1;
    int len=nums.size();

    for(int i=0;i<len;++i)
    {
        while(nums[i]>0&&nums[i]<len&&nums[nums[i]-1]!=nums[i])
        {
            swap(nums[i],nums[nums[i]-1]);
        }
    }

    for(int i=0;i<len;++i)
    {
        if(nums[i]!=i+1) return i+1;
    }
    return len+1;
}

时间复杂度：O(n)O(n)

虽然有两个循环，但是其实while 循环不会每一次都把数组里面的所有元素都看一遍。如果有一些元素在这一次的循环中被交换到了它们应该在的位置，那么在后续的遍历中，由于它们已经在正确的位置上了，代码再执行到它们的时候，就会被跳过。所以时间复杂度为O(n)O(n)。

空间复杂度：O(1)O(1)