LeetCode41. [H]缺失的第一个正数

41. 缺失的第一个正数 - 力扣（LeetCode）

一、思路

本题难度主要体现在要求时间复杂度为O(n)​ , 空间复杂度为O(1)​,否则我们可以借助排序轻易的解决，如：

class Solution
{
public:
    int firstMissingPositive(vector<int> &nums)
    {
        // 不满足要求的 onlogn o1
         int n = nums.size();
        //排序 nlogn
        sort(nums.begin(), nums.end());
        if (nums[n - 1] < 1 || nums[0]>1)
            return 1;

        int i = 0;
        int prev;
        
        bool flag=false;
        while (i < n)
        {
            if (nums[i] < 1)
            {
                i++;
                continue;
            }
            //从第二个开始判断当前的元素是否等于prev+1
            if (flag && nums[i] != prev + 1 && nums[i]!=prev)
            {
                return prev + 1;
            }
            //如果排序后的第一个元素大于1，可以直接得出结果
            if (!flag)
            {
                if(nums[i]>1) return 1;
                flag = true;
            }
            prev = nums[i];
            i++;
        }
        return nums[n - 1] + 1;
    }
};

PS:以上代码可以通过所有测试用例，但时间复杂度不符合题目要求，用flag有点蠢（不知道自己当时为什么会这么写，但笔者比较懒，就不修改了），其实可以排序后直接判断nums[0]是不是大于1即可。

或者我们还可以借助哈希表（On，On），轻易解决问题，但复杂度仍不满足题目要求

‍

对于一个长度为n的数组，其未出现的最小正整数一定在区间[1,n+1]中

• 如果[1,n]都出现了 那么最小正整数一定是n+1
• 如果[1,n]没有都出现，那么最小正整数一定在[1,n]之间

‍

二、解题方法

2.1 标记法

我们可以对所有出现过且​​数值<=n​​的数num，将数组中下标为num-1(防止越界)的位置的数值设置为-num

为什么要设置为-num呢？ 因为在标记过程中，我们可能会改变未标记元素，但标记为​ ​-num​​，可以让我们借助​​math.abs()​ ​获得原本的数值

但数组中原有的负数会对此造成影响，所以我们可以提前将负数的数值​​设置为n+1​​ ,避免负数造成的影响 （负数本身不会影响我们得出缺失的最小正整数，只有正数才会对结果有影响，我们将其设置为n+1，就可以跳过对负数的处理）

最后数组中第一个不是负数的元素所​​对应的下标+1​​（凡是出现过的正数num，nums[num-1]=负数），就是缺失的第一个正数。

2.1.1 代码：

class Solution
{
public:
    int firstMissingPositive(vector<int> &nums)
    {

        // 标记法
        // 关键在在于nums的长度为n 那么未出现的最小正整数 一定在[1,n+1]
        // 如果[1,n]都出现了 那么最小正整数一定是n+1
        // 如果[1,n]没有都出现，那么最小正整数一定在[1,n]之间
        int n = nums.size();
        // 将所有的负数转化为正数且设置为n+1
        for (int &num : nums)
        {
            if (num <= 0)
            {
                num = n + 1;
            }
        }
        // 如果一个数num小于n 就将nums[num-1](减1防止越界)设置为负数
        for (int i = 0; i < n; i++)
        {
            // 用绝对值，是因为我们会边标记边遍历，数组是无序的，
            // 防止误判因标记被改变的元素（负数，但原数据<n：需要标记原数据 负数,原数据>n:不应该标记）
            int num = abs(nums[i]);
            if (num <= n)
            {
                //保证设置为负数
                nums[num - 1] = -abs(nums[num - 1]);
            }
        }
        // 第一个不是负数的下标+1就是最小正整数
        for (int i = 0; i < n; i++)
        {
            if (nums[i] > 0)
            {
                return i + 1;
            }
        }
        // // 否者就是n+1
        return n + 1;
    }
};

2.1.2 复杂度分析

• 时间复杂度：O(N)，其中 N 是数组的长度。
• 空间复杂度：O(1)。

2.2 置换法

本质上依旧是采取某种手段标记出现过的正数，有点类似于选择排序的思想，把一个数放在他应该呆在的位置

最后，凡是出现过的数值属于​ ​[1,n]​ ​区间的元素，假定其数值为num，其都会被放在数组中下标为 ​num-1的位置​​

这种方法应该更容易理解

2.2.1 代码：

class Solution
{
public:
    int firstMissingPositive(vector<int> &nums)
    {
        // 置换法
        int n= nums.size();
        for(int i=0;i<n;i++)
        {
            //将[1,n]且其数值-1对应的下标不等于自己（nums[i]!=nums[nums[i]-1]）,就将其放到自己应该所处的位置
            while(nums[i]>0&&nums[i]<=n&&nums[i]!=nums[nums[i]-1])
            {
                swap(nums[nums[i]-1],nums[i]);
            }
        }
        for(int i=0;i<n;i++)
        {
            //第一个数值不等于下标+1的元素 下标+1就是缺失的第一个正数
            if(nums[i]!=i+1)
            {
                return i+1;
            }
        }
        return n+1;
    }
};

2.2.2 复杂度分析

• 时间复杂度：O(N)，其中 N 是数组的长度。
• 空间复杂度：O(1)。

三、参考

41. 缺失的第一个正数（官方题解）

四、结语

其实有些不解为什么非要用on o1来解决这个问题？

‍

本文介绍了LeetCode第41题“缺失的第一个正数”的解法。题目要求在O(n)时间复杂度和O(1)空间复杂度下找到数组中缺失的最小正整数。作者首先分析了常规排序和哈希表方法的不足，然后提出了基于标记法的优化方案：通过将负数设为n+1排除干扰，利用数组下标标记出现过的正数，最终通过扫描数组确定缺失的最小正整数。该方法高效且满足题目要求。