<div>
Given an unsorted integer array nums, return the smallest missing positive integer.
You must implement an algorithm that runs in O(n) time and uses constant extra space.
Example 1:
<pre>Input: nums = [1,2,0] Output: 3 </pre>
Example 2:
<pre>Input: nums = [3,4,-1,1] Output: 2 </pre>
Example 3:
<pre>Input: nums = [7,8,9,11,12] Output: 1 </pre>
Constraints:
1 <= nums.length <= 5 * 10<sup>5</sup>-2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1
</div>
题目大意：
找第一个缺失的正整数
解题思路：
类似于quick sort里面的partition，满足某些条件才移动指针
解题步骤：
N/A
注意事项：
- 第一个正确元素为1，所以预期数组为[1, 2, 3...]，从1开始并不是从0开始。
- 交换元素的条件：需要交换nums[i] != i + 1, 可以交换[1 <= nums[i] <= len(nums)], 不会死循环(nums[nums[i] - 1] != nums[i])
- 若满足条件，无限交换，直到不满足条件。不满足条件才移动遍历指针i
- 交换两元素涉及内嵌数组，所以不能用comment上的。
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17def firstMissingPositive(self, nums: List[int]) -> int:
i = 0
while i < len(nums):
if nums[i] != i + 1 and 1 <= nums[i] <= len(nums) and nums[nums[i] - 1] != nums[i]:
# nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]
self.swap(nums, i, nums[i] - 1)
else:
i += 1
j = 1
while j <= len(nums):
if j != nums[j - 1]:
break
j += 1
return j
def swap(self, nums, i, j):
nums[i], nums[j] = nums[j], nums[i]
算法分析：
时间复杂度为O(n)，空间复杂度O(1)
