[LeetCode]41. 缺失的第一个正数(First Missing Positive)

题目描述

给定一个未排序的整数数组,找出其中没有出现的最小的正整数。

示例 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. 遍历数组,判断 1 是否在数组中,并将非正数、大于 n 的数修改为 1(n+1 最后来判断)。现在数组中所有的数字都为正数;
  2. 若 1 不在数组中,直接返回;
  3. 若 1 在数组中:
    1. 数组长度为 1,返回 2;
    2. 遍历数组,以数组中每个位置上的数字为索引,将索引对应位置的数字修改为负数,表示该位置的索引存在于数组中。由于遇到数字 n 时没有索引 n,故使用索引 0 表示索引 n;
    3. 现在数组中所有位置上的数字都为负数,除了没有出现过的数字的位置(如 2 不在原数组中,那么现在的数组索引为 2 的位置数字大于 0);
    4. 遍历数组索引为 1 到末尾的所有数,第一个大于 0 即为结果;
    5. 若未找到,看索引 0 位置的数字(表示的是数字 n);
    6. 若未找到,即现在的数组都为负数,说明都被修改过,说明原数组刚好为 1 到 n,则缺失的最小正数为 n+1

最后说一句:LeetCode 的 hard 还是 hard!(你大爷还是你大爷!)

代码

Python 3.6

1
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
34
class 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

参考

https://leetcode-cn.com/problems/first-missing-positive/solution/que-shi-de-di-yi-ge-zheng-shu-by-leetcode/

文章目录
  1. 1. 题目描述
  2. 2. 解题思路
  3. 3. 代码
  4. 4. 参考
|

载入天数...载入时分秒...