刷题使我快乐，满脸开心.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
}