LeetCode41.缺失的第一个正数-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode41.缺失的第一个正数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

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

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

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

思路：

1.本题在有刷过代码随想录的哈希表部分基础后很容易想到用数组来充当哈希表，但是在数组下标与数组元素的映射上还需要仔细想想。

2.一开始以为是直接用数组下标来表示哈希表的键，数组元素就是对应数组下标的数字的值。然后我们遍历原数组，将有的正数在其对应的下标处置为1。虽然想法很美好，但是写出如下代码后不难发现问题：

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int hash[50001] = {0};
        int res = 1;

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

            if(res == nums[i]){
                res++;
            }
        }

        for(int i = 0; i < 50001; i++){
            if(hash[i] != 0 && res == i){
                res++;
            }
        }

        return res;
    }
};

没错，题目中i的取值范围是[0,50000]，而nums[i]的取值范围是[-2 ^ 31, 2^31 - 1]，此时显然不可能用数组下标来表示了。

3.在看了一些大佬的题解后才发现自己的思路大方向是对的但细节上差了一些。首先因为题目要求的是空间复杂度为O（1），因此我们不能额外申请新的数组，那么就只能在原数组上操作了。

要找缺失的第一个正数，对于长度为n的数组，这个正数只可能是[1, n + 1]，既然数组下标是从0开始，我们就找到了一个映射——大小为i的数，应当放置在下标为i - 1的位置。如果遍历完数组后[1,n]的数字均放置在了对应的位置上，那么缺失的第一个正数就是n + 1。

4.有了以上思路后，我们就遍历整个数组，如果当前下标i的元素在[1,n]的范围内，我们就将其与nums[nums[i] - 1]的位置进行交换（如示例2中，nums[0]为3,3应当放置到nums[2]的位置），直到当前下标i的数字为负数或者满足nums[i] = nums[nums[i] - 1]为止。文章来源地址https://www.toymoban.com/news/detail-521312.html

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

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

        return n + 1;
    }
};

到了这里，关于LeetCode41.缺失的第一个正数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！