我的博客

leetcode 41. 缺失的第一个正数

目录
  1. 题目概括
  2. 解法

https://leetcode-cn.com/problems/first-missing-positive/

题目概括

给定正数数组 nums,返回数组中没有的最小的一个正整数。

要求:时间复杂度 O(n),空间复杂度 O(1)

解法

这个题目的巧妙之处在于利用了输入的数组做标记,这样省去了使用额外空间,从而实现了 O(1) 的空间复杂度。

关键点是:设数组长度为 n,那么答案一定在 [1, n+1] 之中。这是显而易见,因为 nums 里只有 n 个数,不可能出现 [1, n+1] 里的所有数字。

如果想实现 O(n) 的时间复杂度,只能遍历,不能排序,这里的方法是

处理特殊情况,如果 1 不再 nums 里,答案自然是 1。否则:

首先除掉数组中 [1, n+1] 以外的数,因为他们根本不会影响结果,干脆把这些数都写成 1。

然后,nums 里只有正数了,而且值在 [1, n] 之内。我们遍历数组,对于数组里每个数字,令 nums 对应的第这个位置的数变成负数。就把所有数的位置标记出来了,相当于用了一个桶排序算法

然后再遍历一下,第一个不是负数的位置就是缺失的数了。

这里需要特殊处理 n,因为 n 会越界,干脆用位置 0 代表 n,或者也可以把所有数统一减一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
if 1 not in nums:
return 1
n = len(nums)
for i in range(n):
if nums[i] > n or nums[i] <= 0:
nums[i] = 1
for i in range(n):
a = abs(nums[i])
if a == n:
nums[0] = -abs(nums[0])
else:
nums[a] = -abs(nums[a])
for i in range(2, n):
if nums[i] > 0: return i
return n if nums[0] > 0 else n+1

评论无需登录,可以匿名,欢迎评论!