每日一题：LeetCode-41. 缺失的第一个正数

作者：半亩房顶

2023-12-01
北京
本文字数：1586 字
阅读完需：约 5 分钟

刷题使我快乐，满脸开心.jpg

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/first-missing-positive/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你一个未排序的整数数组 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 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1

思路

源于自己的思路整理 + 各位大神和官方题解的规范及矫正

这道题如果没有空间复杂度的限制，那么就很简单了，直接一个哈希表，然后缺失的最小数字就是结果了。但是很可惜，有空间复杂度的限制。那么，我们来顺着一个问题想下如何解决：

为什么需要哈希表？多大容量的哈希表就够用了？

1、为什么需要哈希表

用哈希表的理由很简单，我们需要找到缺失位置，而哈希表是一个能够用值来做标记表示某个位置是否有缺失的数据结构

2、多大容量的哈希表就够用了

乍一听可能有点想笑，毕竟一共只有数组长度个值，那么自然是需要n=len(nums)的长度就够用了嘛~

那么，我们综合一下这两个问题的答案：

我们其实真正要的，是一个n长度 和 能够做标记表示位置是否缺失的数据结构

那么

原本就有的 nums 可以吗？

当然可以

但是有人会说了，利用nums来做标记可以是可以，比如转成负数、替换成某个值等等等等，但是，nums 中可能存在各种各样的数字啊，比如本身就是负数、本身就是个随机的值，这怎么办呢？

还有一个根本性的思路：

对于一个 n 长度的数组来说，缺失的最小正整数，要么在1到n之间，要么就是n+1

因为一共就n个数，就算恰好是1到n，那么最小的正整数就是n+1，而一旦有范围外的数字，那最小的正整数肯定就在1到n之间了

所以到这里思路应该就出来了

负数标记法

用负数的方式做标记

把负数都替换成n+1
遍历数组，如果数字的绝对值在1到n之间，那么就把对应位置的数字置为负数
再遍历处理完的数组，如果某个位置不是负数，那么这个位置对应的数字i+1就是结果；如果所有位置都是负数，那么结果就是n+1

置换位置法

用换位置的方式做标记

遍历数组，如果数字在1到n之间，那么就把数字换到正确位置；当然如果对应位置数字就是正确的就不用换了~
遍历处理完的数组，如果某个位置不对应，那么这个位置对应的数字i+1就是结果；如果所有位置都是对应的，那么结果就是n+1

至此，上代码。

代码

负数标记

func firstMissingPositive(nums []int) int {    n := len(nums)    for i := 0; i < n; i++ {        if nums[i] <= 0 {            nums[i] = n + 1        }    }    for i := 0; i < n; i++ {        num := abs(nums[i])        if num <= n {            fmt.Println(num-1)            nums[num - 1] = -abs(nums[num - 1])        }    }    for i := 0; i < n; i++ {        if nums[i] > 0 {            return i + 1        }    }    return n + 1}
func abs(a int) int {    if a < 0 {        return -a    }    return a}

复制代码

位置置换

func firstMissingPositive(nums []int) int {    n := len(nums)    for i := 0; i < n; i++ {        // 如果是在1到n之间的数字，那就让它归位        // 不过注意如果其正确位置上的数字就是对的，那就别再换了        for nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i]-1] {            nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]        }    }    // 第一个没能归位的就是缺失的，也就是最小缺失正整数    for i := 0; i < n; i++ {        if nums[i] != i+1 {            return i+1        }    }    // 所有位置都归位了（1到n都齐了），那最小缺失正整数就是n+1    return n+1}

复制代码

欢迎关注公众号查看更多题目~

发布于: 刚刚阅读数: 6

原文链接:【http://xie.infoq.cn/article/960e616cd9d491ad2b2efd094】。文章转载请联系作者。

半亩房顶

关注

人生那么长，能写多少bug？ 2018-11-16 加入

我希望，自己永远是自己。我希望，远离bug。

发布

暂无评论

创作场景

每日一题：LeetCode-41. 缺失的第一个正数

题目

思路

1、为什么需要哈希表

2、多大容量的哈希表就够用了

当然可以

还有一个根本性的思路：

负数标记法

置换位置法

代码

负数标记

位置置换

半亩房顶

评论