☆打卡算法☆LeetCode 41、缺失的第一个正数 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“找到数组中，没有出现过的最小正整数。”

题目链接：

来源：力扣（LeetCode）

链接：41. 缺失的第一个正数 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

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

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

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

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

二、解题

1、思路分析

这道题需要找到数组中不存在最小正整数，这个还是很容易实现的。

第一种方法用哈希表，将数组中所有的数字存到哈希表中，然后从1开始枚举正整数，判断是否在数组中，时间复杂度O(N)，空间复杂度O(N)。

第二种方法遍历枚举，从1开始枚举正整数，然后遍历数组，判断这个数字是否在数组中，时间复杂度O(N²)，空间复杂度O(1)。

但是，题目要求是时间复杂度O(N)，空间复杂度O(1)，解题容易，但是满足题意还是很难的。

只能修改算法，利用数组中的空间来存储一些状态。

2、代码实现

代码参考：

public class Solution
{
    public int FirstMissingPositive(int[] nums)
    {
        for (int i = 0; i < nums.Length; i++)
        {
            while(nums[i]>0&&nums[i]<=nums.Length
                 && nums[i] != nums[nums[i] - 1])
            {
                var next = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = next;
            }
        }

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

    public int FirstMissingPositive1(int[] nums)
    {
        var add = 0;
        for (int i = 0; i < nums.Length; i++)
        {
            while (nums[i] >= 0 && nums[i] < nums.Length
                 && nums[i] != nums[nums[i]])
            {
                var temp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = temp;
            }
            if (nums[i] == nums.Length)
            {
                add = 1;
            }
        }
        for (int i = 1; i < nums.Length; i++)
        {
            if (nums[i] != i)
            {
                return i;
            }
        }
        return add + nums.Length;
    }
}

3、时间复杂度

时间复杂度 ： O(N)

其中 N 是数组的长度。

空间复杂度： O(1)

只需要常数级别的空间存放变量。

三、总结

本题的难点在：只能使用常数级别的额外空间，在这个限制下本题的思路有一个非正式的名称：原地哈希。

就是将数组视为哈希表，这个思路就相当于我们自己编写哈希表。

哈希表的规则很简单，那就是数值为i的数映射到下标为i-1的位置。