LeetCode 041 First Missing Positive

LeetCode

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:

Input: nums = [1,2,0]
Output: 3

Example 2:

Input: nums = [3,4,-1,1]
Output: 2

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1

Constraints:

`1 <= nums.length <= 5 10<sup>5</sup>*-2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1`

题目大意：

找第一个缺失的正整数

解题思路：

类似于quick sort里面的partition，满足某些条件才移动指针

解题步骤：

N/A

注意事项：

1. 第一个正确元素为1，所以预期数组为[1, 2, 3…]，从1开始并不是从0开始。
2. 交换元素的条件：需要交换nums[i] != i + 1, 可以交换[1 <= nums[i] <= len(nums)], 不会死循环(nums[nums[i] - 1] != nums[i])
3. 若满足条件，无限交换，直到不满足条件。不满足条件才移动遍历指针i
4. 交换两元素涉及内嵌数组，所以不能用comment上的。

Python代码：

def 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)