LeetCode41 缺失的第一个正数

LeetCode 第41题

问题描述

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

示例 1:

1
2
输入: [1,2,0]
输出: 3

示例 2:

1
2
输入: [3,4,-1,1]
输出: 2

示例 3:

1
2
输入: [7,8,9,11,12]
输出: 1

说明:

你的算法的时间复杂度应为O(n),并且只能使用常数级别的空间。

解题思路

解决本题时,第一反应是先对数组进行排序,然后再遍历数组,查找未出现的最小正整数。显然,在时间复杂度以及空间复杂度上不能满足题目要求。

解决本题的核心思路是需要理解这句话:给定一个数组,其大小为n,那么存在未出现的最小正整数$N_{min}$,满足$N_{min} \in [1, n+1]$。

于是,可以遍历数组,使得当前数组元素e与数组下标为e-1的元素进行交换,得到新的数组。最后再遍历新的数组,如果当前下标i不等于数组元素i+1,则i+1为$N_{min}$。比如:

给定数组3, 4, -1, 1

  1. 交换 3-1,则有 -1, 4, 3, 1-1<0停止交换,继续下一个元素遍历
  2. 交换41,则有-1, 1, 3, 4,继续交换,1, -1, 3, 4
  3. 交换3
  4. 交换4
  5. 最终得到数组 1, -1, 3, 4

遍历数组,当遍历到第2个元素时,发现2 != (-1 -1),则找到最小正整数2

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""

n = len(nums)

for i in range(n):
while 0 < nums[i] <= n and (nums[i] != i + 1) and (nums[i] != nums[nums[i]-1]):
# nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i] # right?
tmp = nums[nums[i]-1]
nums[nums[i]-1] = nums[i]
nums[i] = tmp

for i in range(n):
if i + 1 == nums[i]:
continue
return i + 1

return n + 1

注意在交换nums[i]nums[nums[i]-1]时,以下代码是否正确:

1
nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
感谢你对我的支持,让我继续努力分享有用的技术和知识点