41.缺失的第一个正数

标记，置换，https://leetcode.cn/problems/first-missing-positive/

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

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

提示：

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1

这个解法，使用了集合，不满足题面“使用常数级别额外空间”。

python

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [-1]*(n+1)
        minv = 1
        visited = set()
        for i in nums:
            if i < 1:
                continue
            visited.add(i)
            if minv == i:
                tmp = minv + 1
                while tmp in visited:
                    tmp += 1
                minv = tmp
        return minv

LeetCode题解：

https://leetcode.cn/problems/first-missing-positive/solutions/304743/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/

实际上，对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1,N+1] 中。这是因为如果 [1,N] 都出现了，那么答案是 N+1，否则答案是 [1,N] 中没有出现的最小正整数。这样一来，我们将所有在 [1,N] 范围内的数放入哈希表，也可以得到最终的答案。而给定的数组恰好长度为 N，这让我们有了一种将数组设计成哈希表的思路：

我们对数组进行遍历，对于遍历到的数 x，如果它在 [1,N] 的范围内，那么就将数组中的第 x−1 个位置（注意：数组下标从 0 开始）打上「标记」。在遍历结束之后，如果所有的位置都被打上了标记，那么答案是 N+1，否则答案是最小的没有打上标记的位置加 1。

那么如何设计这个「标记」呢？由于数组中的数没有任何限制，因此这并不是一件容易的事情。但我们可以继续利用上面的提到的性质：由于我们只在意 [1,N] 中的数，因此我们可以先对数组进行遍历，把不在 [1,N] 范围内的数修改成任意一个大于 N 的数（例如 N+1）。这样一来，数组中的所有数就都是正数了，因此我们就可以将「标记」表示为「负号」。算法的流程如下：

我们将数组中所有小于等于 0 的数修改为 N+1；

我们遍历数组中的每一个数 x，它可能已经被打了标记，因此原本对应的数为 ∣x∣，其中 ∣∣ 为绝对值符号。如果 ∣x∣∈[1,N]，那么我们给数组中的第 ∣x∣−1 个位置的数添加一个负号。注意如果它已经有负号，不需要重复添加；

在遍历完成之后，如果数组中的每一个数都是负数，那么答案是 N+1，否则答案是第一个正数的位置加 1。

python

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            if nums[i] <= 0:
                nums[i] = n + 1
        
        for i in range(n):
            num = abs(nums[i])
            if num <= n:
                nums[num - 1] = -abs(nums[num - 1])
        
        for i in range(n):
            if nums[i] > 0:
                return i + 1
        
        return n + 1

复杂度分析

时间复杂度：O(N)，其中 N 是数组的长度。

空间复杂度：O(1)。

方法二：置换

这是一个经典的原地哈希（In-place Hash）问题。题目要求在 $O (n)$ 时间复杂度和 $O (1)$ 额外空间复杂度的限制下，找出没有出现的最小正整数。

解题思路

对于一个长度为 $n$ 的数组，其中未出现的最小正整数一定在区间 $[1, n + 1]$ 内。可以利用数组本身作为哈希表，尝试将每一个在 $[1, n]$ 范围内的整数 $x$ 放到它应该在的位置，即索引为 $x - 1$ 的位置上。

原地置换：遍历数组，当遇到一个处于 $[1, n]$ 范围内的数值 nums[i] 时，如果它没有在正确的位置（即 nums[nums[i] - 1] != nums[i]），就将它与正确位置上的元素进行交换。我们使用 while 循环不断进行这个交换过程，直到当前位置的值不在 $[1, n]$ 范围内，或者已经满足 nums[nums[i] - 1] == nums[i]。
寻找缺失值：完成置换后，再次遍历数组。第一个满足 nums[i] != i + 1 的索引 $i$ ，其对应的 $i + 1$ 就是缺失的最小正整数。如果数组中的所有位置都满足 nums[i] == i + 1，说明 $1$ 到 $n$ 都出现了，那么缺失的最小正整数就是 $n + 1$ 。

Python 代码实现

python

from typing import List

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        
        for i in range(n):
            # 将在 [1, n] 范围内的数字交换到它应该在的位置 nums[i] - 1
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                # 记录目标交换索引，避免在多重赋值时由于 nums[i] 改变而导致索引出错
                target_idx = nums[i] - 1
                nums[i], nums[target_idx] = nums[target_idx], nums[i]
        
        # 寻找第一个不满足 nums[i] == i + 1 的位置
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        
        # 如果 1 到 n 都存在，则缺失的是 n + 1
        return n + 1

复杂度分析

时间复杂度： $O (n)$ 。虽然在第一步中使用了嵌套的 while 循环，但每一次成功的交换都会将至少一个数放到它的最终正确位置。因为一个数最多被放到正确位置一次，所以整个数组的总交换次数不会超过 $n$ 次。因此，整体时间复杂度为线性。
空间复杂度： $O (1)$ 。直接在原数组上进行修改，只使用了常数个辅助变量，满足题目要求的常数级别额外空间。

【尹显齐物院】做了 30179 的同学们都知道，这个题依旧要用到置换的思想，每次置换一个数使得他到自己对应的位置上（具体而言，将数字 $i$ 放到下标为 $i - 1$ 的位置上），除非当前的数超出 $1 - n$ 的范围，与之前的数重复或已经在它该在的位置上。最后从头开始遍历一遍直到位置与数字不对应的情况发生为止。由于每次都能将一个数放到对应位置上，所以操作次数最多为 $n$ 次，时间复杂度为 $O (n)$ 。

python

class Solution(object):
    def firstMissingPositive(self,nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l = len(nums)
        ans = l+1
        for i in range(l):
            while nums[i] != i+1 and 0<nums[i]<=l:
                if nums[nums[i]-1] == nums[i]:# 重复的数换掉
                    nums[i] = l+2
                    break
                a,b = nums[nums[i]-1],nums[i]
                nums[nums[i]-1],nums[i] = b,a# 注意顺序
        for i in range(l):
            if nums[i] != i+1:
                ans = i+1
                break
        return ans

41.缺失的第一个正数 ​

41.缺失的第一个正数