题目描述
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
说明:
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
解题思路
“哈希表”。直接使用哈希表空间复杂度达不到 O(1)，故使用以自身为索引的哈希表。
注：设数组长度为 n，则结果最大为 n+1；故大于 n+1 的数和负数和零可直接跳过。
步骤：
- 遍历数组，判断 1 是否在数组中，并将非正数、大于 n 的数修改为 1（n+1 最后来判断）。现在数组中所有的数字都为正数；
- 若 1 不在数组中，直接返回；
- 若 1 在数组中：
- 数组长度为 1，返回 2；
- 遍历数组，以数组中每个位置上的数字为索引，将索引对应位置的数字修改为负数，表示该位置的索引存在于数组中。由于遇到数字 n 时没有索引 n，故使用索引 0 表示索引 n；
- 现在数组中所有位置上的数字都为负数，除了没有出现过的数字的位置（如 2 不在原数组中，那么现在的数组索引为 2 的位置数字大于 0）；
- 遍历数组索引为 1 到末尾的所有数，第一个大于 0 即为结果；
- 若未找到，看索引 0 位置的数字（表示的是数字 n）；
- 若未找到，即现在的数组都为负数，说明都被修改过，说明原数组刚好为 1 到 n，则缺失的最小正数为 n+1
最后说一句：LeetCode 的 hard 还是 hard！（你大爷还是你大爷！）
代码
Python 3.61
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
have_1 = False
for idx in range(n):
if nums[idx] == 1:
have_1 = True
if nums[idx] <= 0 or nums[idx] > n:
# 将所有非正数和大于 n 的数都改为 1
nums[idx] = 1
if not have_1:
# 没找到 1，则结果为 1
return 1
if n == 1:
# 总长为 1，且找到了 1，则结果为 2
return 2
for idx in range(n):
tmp = abs(nums[idx])
if tmp == n:
# 数字 n 是否存在，因为没有索引 n，故修改索引 0
nums[0] = -abs(nums[0])
else:
nums[tmp] = -abs(nums[tmp])
for idx in range(1, n):
# 先遍历 1 到 n-1 看是否有结果
if nums[idx] > 0:
return idx
if nums[0] > 0:
# 再看存放 n 的结果的索引 0 处
return n
# 都存在说明数组刚好是 1 到 n
return n + 1执行用时 : 48 ms内存消耗 : 13.7 MB