[41][困难][原地哈希] 缺失的第一个正数

题目描述

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

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

解题思路

原地哈希

Leetcode官方题解: 缺失的第一个正数

使用哈希表可以很简单的解决这个问题, 例如:

我们可以将数组所有的数放入哈希表，随后从 11 开始依次枚举正整数，并判断其是否在哈希表中
我们可以从 11 开始依次枚举正整数，并遍历数组，判断其是否在数组中

但使用额外的哈希表, 空间复杂度就不是常数级别的了. 我们可以考虑使用原始的数组, 进行原地的哈希. 而数组的原地哈希, 就需要长度为 $N$ 数组的每个位置都有意义, 还能找到一种元素的置换方法.

对于一个长度为 $N$ 的数组, 其中没有出现的最小正整数只能在 $[1, N+1]$ 中. 因为如果 $[1, N]$ 的每个数字都在数组中出现过, 则第一个缺失的整数就是 $N+1$ ; 如果 $[1, N]$ 中有数字没有出现过, 其中没有出现过的最小值就是缺失的第一个正数.

因此我们将原始列表的每个位置表示对应的数字是否在列表中出现过. 需要注意的是, 因为找的是缺失的正数, $[1, N]$ 共 $N$ 个数字, 因此对于数字 $i$ , 对应的索引为 $i-1$ .

需要解决的冲突点是, 由于是在原始的数组上进行哈希, 从头开始迭代时, 遇到某个数字, 需要将这个数字对应的位置进行标记, 但这个位置还有数字待处理. 解决这个矛盾, 有两种方法:

循环替代: 将对应位置的数字置换过来, 对应位置打上标记, 代表出现过, 然后继续处理置换过的这个新的数字
- 关键在于置换的停止条件:
  - 置换过来的数字不在 $[1, N]$ 范围内, 这个数字无序处理, 而且不在范围内也无法处理. 这个数字对最后的结果也没有影响, 就放在当前位置上, 结束内循环置换, 外层迭代推进到下一个位置
  - 要置换到的位置已经被标记, 相当于这个数字重复出现, 当前的这个数字也无序处理了
- 这样哈希数组的每个位置意义就是单纯的是否出现过的标志
意义融合: 上面的方法, 哈希数组每个位置的意义是对应的数字是否出现过. 意义融合的方法, 哈希数组每个位置的意义, 要融合原始的数值, 以及是否出现过的标记

考虑第二种方法, 如何融合.

先对数组进行遍历, 由于不在范围内的数字对结果没有影响, 把不在 $[1, N]$ 范围内数修改成任意一个大于 $N$ 的正数, 这样数组中的所有数就都是正数了. 因此就可以在标记出现的时候, 将对应位置的数值加上符号, 数字为负表示位置对应的正数出现过, 而取绝对值后的数值就是数组中原来的数值.

整体流程如下:

我们将数组中所有小于等于 0 的数修改为 $N+1$
我们遍历数组中的每一个数 $x$ ，它可能已经被打了标记，因此原本对应的数为 $|x|$ ，其中 $|\,|$ 为绝对值符号。如果 $|x| \in [1, N]$ ，那么我们给数组中的第 $|x| - 1$ 个位置的数添加一个负号。注意如果它已经有负号，不需要重复添加
在遍历完成之后，如果数组中的每一个数都是负数，那么答案是 $N+1$ ，否则答案是第一个正数的位置加 1

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

        for i in range(n):
            num = abs(nums[i])
            if 1 <= num <= n:
                nums[num - 1] = -abs(nums[num - 1])

        for i in range(n):
            if nums[i] > 0:
                return i + 1
        return n + 1

最后更新于3年前