LeetCode41 缺失的第一个正数

问题描述

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

示例 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

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

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

Code

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]