当前位置 博文首页 > zhang_han666的博客：leetcode41. 缺失的第一个正数
题目：
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
提示：
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
思路：
题目的意思是数组不能事先排好序，而且对空间和时间有要求。
1. 官方题解用了一个很巧妙的哈希，用了题目的一个隐藏条件：即任意给定数组的解必定小于等于数组的长度加1。
哈希表是这样建立的：键是数组的索引，值是索引处存的值的正负号，表示这个索引是否在数组中出现（负号表示出现）。用0的位置的正负号来映射 数组长度这个值是否出现在数组中。
由于我们用值的正负号来标记索引是否出现在数组中，因此我们需要把数组中的负数改为1，可以顺便把大于数组长度的值也置为1。
由于人为置1，所以我们需要事先检查1是否出现，没出现直接返回1。需要注意避免重复改变符号。
2. 同样利用任意给定数组的解必定小于等于数组的长度加1这个条件，我们可以把大于等于1小于等于数组长度的数放到有序对应的索引位置。最后检查索引处的值是不是等于索引加1，不等于就说明没出现过。
代码1：
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
if 1 not in nums:
return 1
# [1] 这种情况
if len(nums) == 1:
return 2
for i in range(len(nums)):
if nums[i] <= 0 or nums[i] > len(nums):
nums[i] = 1
for i in range(len(nums)):
temp = abs(nums[i])
if temp == len(nums):
# 注意这块的abs，是为了避免重复改变符号。
nums[0] = -abs(nums[0])
else:
nums[temp] = - abs(nums[temp])
for i in range(1, len(nums)):
if nums[i] > 0:
return i
if nums[0] > 0:
return len(nums)
return len(nums) + 1
代码2：
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
# 注意此处是while不是if，因为交换之后i处的值有可能需要继续被交换。
while 1<=nums[i] and nums[i]<=n and nums[i] != nums[nums[i]-1]:
temp = nums[i]-1
nums[i], nums[temp] = nums[temp], nums[i]
for i in range(n):
if nums[i] != i+1:
return i+1
return n+1
