缺失的第一个正数

题面

给你一个未排序的整数数组 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 <= 105
• -231 <= nums[i] <= 231 - 1

分析

• 可以使用 unordered_set 来记录已经遇到的正整数，并使用 result 来记录已经遇到的最大连续正整数

• 最后一直没有遇到的即为结果

• 代码实现

  class Solution {
  public:
      int firstMissingPositive(vector<int>& nums) {
          std::unordered_set<int> set;
          int result = 1;
          for (int n : nums) {
              if (n <= 0)
                  continue;
              if (n == result) {
                  while (set.find(++result) != set.end())
                      ;
              }
              set.insert(n);
          }
          return result;
      }
  };

• 这个实现的时间复杂度为 $O(n)$，但是当数组特别大时，哈希碰撞越来越明显，可能会拖慢速度

• 同时，空间复杂度为 $O(n)$，没有满足题目中的进阶要求，那么有可以改进的方法吗？

• 显然，一个长度为 n 的数组所能表示的最大正整数为 n，其对应结果应该是 n+1

• 那么当遇到一个正整数 i 时，如果 i-1 < n，那么就可以将 nums[i-1] 处的数字换为 i，表示数字 i 已经找到

• 在交换数字之和，注意要处理被换到当前位置的新的数字

• 最后遍历数组，遇到第一个其下标 idx+1 ≠ nums[idx] 时，说明其就是待返回的结果

• 代码实现如下

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

• 实际上，这是一种原地哈希技巧，即 $f(nums[i])=nums[i]-1$