题目
41. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。
提示：
- 1 <= nums.length <= 105
- -231 <= nums[i] <= 231 – 1
我的代码（Python）
version 1
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
numsSet = set(nums)
i = 1
while i in numsSet:
i += 1
return i最直观的解法，使用标准库里的set实现。不过这样总觉得是在取巧……另外空间复杂度也没有达到O(1)。
version 2
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
nums.sort()
result = 1
for num in nums:
if num <= 0:
continue
if num > result:
break
result = num + 1
return result另外一种直观解法，排序。本来以为这样效率会低，结果居然能击败90%？list的排序根据网上的信息，最低是可以达到O(n)，但是一般应该是O(nlogn)级别的，这样也可以满足要求吗？
点评
基本上能想到的，除了哈希就是排序了（哈希其实也算一种排序方式）。
官方果然也是用哈希表，不过这次又不用标准库了，大概是时间复杂度不够。
制作[1, N]作为哈希表，这个想法很巧妙。
我一直想的是需要创建从1到max(nums)的哈希表，这样也太大了；还是思路没有打开。
后面一种置换法在前一种的基础上就比较好想了。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog