原地哈希 | 笑枕晚风の小站

41. 缺失的第一个正数

Difficulty: 困难

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

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

示例 1：

1 2	输入：nums = [1,2,0] 输出：3

示例 2：

1 2	输入：nums = [3,4,-1,1] 输出：2

示例 3：

1 2	输入：nums = [7,8,9,11,12] 输出：1

提示：

1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1

Solution

前言

如果本题没有额外的时空复杂度要求，那么就很容易实现：

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

如果数组的长度为 $N$ , 那么第一种做法的时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ ; 第二种做法的时间复杂度为 $O\left(N^{2}\right)$ ，空间复杂度为 $O(1)$ 。但它们都不满足时间复杂度为 $O(N)$ 且空间复杂度为 $O(1)$ 。

「真正」满足时间复杂度为 $O(N)$ 且空间复杂度为 $O(1)$ 的算法是不存在的，但是我们可以退而求其次：利用给定数组中的空间来存储一些状态。

也就是说，如果题目给定的数组是不可修改的，那么就不存在满足时空复杂度要求的算法;

但如果我们可以修改给定的数组，那么是存在满足要求的算法的。

原地哈希映射

由于题目要求我们「只能使用常数级别的空间」，而要找的数一定在 $[1, \mathrm{~N}+1]$ 左闭右闭（这里 $\mathrm{N}$ 是数组的长度) 这个区间里。因此，我们可以就把原始的数组当做哈希表来使用。事实上，哈希表其实本身也是一个数组;
我们要找的数就在 $[1, N+1]$ 里，最后 $N+1$ 这个元素我们不用找。因为在前面的 $\mathrm{N}$ 个元素都找不到的情况下，我们才返回 $\mathrm{N}+1$ ;
那么，我们可以采取这样的思路：就把 1 这个数放到下标为 0 的位置， 2 这个数放到下标为 1 的位置，按照这种思路整理一遍数组。然后我们再遍历一次数组，第 1 个遇到的它的值不等于下标的那个数，就是我们要找的缺失的第一个正数。
这个思想就相当于我们自己编写哈希函数，这个哈希函数的规则特别简单，那就是数值为 $i$ 的数映射到下标为 $i-1$ 的位置。

Language: c++

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] >= 1 && nums[i] <= n && nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
};

原地数组标记

要标记的数据是 $1\cdots n$ ，而数组可供存储的空间下标是 $0\cdots n-1$ ，所以值为 $i$ 的数要用下标 $i-1$ 的位置空间来存储标记

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

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

算法的流程如下：

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

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

class Solution {
 public:
  int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (auto& x : nums) {
      if (x <= 0) x = INT_MAX;
    }
    for (int i = 0; i < n; ++i) {
      int x = abs(nums[i]);
      if (x <= n) {
        int idx = x - 1;
        nums[idx] = -abs(nums[idx]);
      }
    }
    for (int i = 0; i < n; ++i) {
      if (nums[i] > 0) return i + 1;
    }
    return n + 1;
  }
};