[Leetcode] 41. First Missing Positive

逃离我推掉我的手 2022-06-15 19:56 73阅读 0赞

# 41. First Missing Positive #

Given an unsorted integer array, find the first missing positive integer.

For example,  
Given \[1,2,0\] return 3,  
and \[3,4,-1,1\] return 2.

Your algorithm should run in O(n) time and uses constant space.

## 给定一个未排序的整数数组，找到第一个遗失的整数。 ##

例如：  
给定\[1,2,0\]返回3；  
给定\[3,4,-1,1\] 返回2.

算法时间复杂度为O(n)，并且使用常数空间。

## 解题思路 ##

### 方法一：哈希表 ###

这是一题困难度标记为Hard但是其实很简单的题目。解决这题很自然而然的想到使用哈希表记录出现的数据，然后载扫描一遍数组，找到第一个没出现的整数就可以了。但是哈希表的长度设置是一个问题，因为我们并不知道整数的范围。因此，刚开始的想法是使用两个变量记录整数数组中最大和最小的整数，从而确定哈希表的范围。 但是再继续深入，可以发现其实并不需要这样。因为负数和0不需要考虑，而满足条件的最大整数一定是大于0并且小于n（n为数组的长度）的。因为假设给定的数组都是整数，并且最小的整数是1，那么之后的数字最大只能是n，才能保证中间没有缺失的整数。所以，我们再记录哈希表的时候，不需要考虑负数，0以及小于n的整数。因此，最终的代码如下：

int firstMissingPositive(vector<int>& nums) {
        vector<int> bucket (nums.size(), 0);
        for (int i = 0; i < nums.size(); ++i)
        {
            if (nums[i] > 0 && nums[i] <= nums.size()) {
                bucket[nums[i]-1] = 1;
            }
        }
    
        for (int i = 0; i < nums.size(); ++i)
        {
            if (bucket[i] == 0) 
                return i + 1;
        }
        return nums.size() + 1;
    
    }

### 方法二：桶排序 ###

第二种方法就是使用[桶排序][Link 1] 。其实这种方法跟哈希表方法是一样的思路，只是将hash\[i\] = 1/0 ，变成了bucket\[i\]=i/0。

int firstMissingPositive(vector<int>& nums) {
        vector<int> bucket (nums.size()+1, 0);
        for (int i = 0; i < nums.size(); ++i)
        {
            if (nums[i] > 0 && nums[i] <= nums.size()) {
                bucket[nums[i]] = nums[i];
            }
        }
    
        for (int i = 1; i <= nums.size(); ++i)
        {
            if (bucket[i] != i) 
                return i;
        }
        return nums.size() + 1;
    
    }

但是目前的方法一和方法二的空间复杂度其实都是0（n），能不能再减小一点呢？可以，直接使用原来的数组作为桶，就不需要额外的空间了。如此，当我们发现nums\[i\]!=i+1的时候，就表示需要排序。排序的操作就是交换 nums\[i\] 和 nums\[nums\[i\]-1\]。因此，最终的代码变为：

int firstMissingPositive(vector<int>& nums) {
         int i=0; 
         int n = nums.size();
         while(i<n){  
            if((nums[i] >= 1 && nums[i] <= n) && (nums[i] != i + 1 && nums[nums[i]-1] != nums[i]))  
                swap(nums[i],nums[nums[i]-1]);  
            else  
                i++;  
        }  
        for(int i = 0; i < n;i++){  
            if(nums[i] != i + 1)  
                return i + 1;  
        }  
        return n + 1; 
    }

如此，算法的时间复杂度为O(n)，空间复杂度为O(1)。

[Link 1]: http://www.cnblogs.com/kkun/archive/2011/11/23/2260267.html