Leetcode力扣解题记录--第41题（原地哈希）

题目链接：41. 缺失的第一个正数 - 力扣（LeetCode）

题目描述

给你一个未排序的整数数组 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

 题目作答

这个问题的关键限制是 O(n) 时间复杂度和常数级别额外空间。这排除了使用排序（O(n log n)）或哈希表（O(n) 空间）等直接方法。

正确解法核心思想是将数组本身当作一个哈希表，利用数组的索引来记录数字的出现情况。我们希望实现这样一个状态：如果数字 x 存在，那么它应该被放在数组中索引为 x-1 的位置上。也就是说，我们试图让 nums[i] = i + 1。

具体思路可以分为两步：

1. 原地哈希（元素归位）

   • 我们遍历整个数组，对于遍历到的当前数字 nums[i]：

   • 我们检查这个数字 nums[i] 是否在 [1, n] 这个范围内（其中 n 是数组的长度）。因为只有在这个范围内的数字，才有可能成为我们寻找的那个“最小正整数”。任何负数、0、或者大于 n 的数，对于找到 1 到 n+1 之间的缺失正数是没有帮助的。

   • 如果 nums[i] 是一个在 [1, n] 范围内的有效数字，我们就需要把它放到它“应该”在的位置，也就是索引 nums[i] - 1 的位置。

   • 所以，我们执行一个交换操作：swap(nums[i], nums[nums[i] - 1])。

   • 重要细节：在交换之后，新的 nums[i] 可能仍然不是它应该在的位置，所以我们需要用一个 while 循环，持续地将 nums[i] 放到正确的位置，直到 nums[i] 不再是 [1, n] 范围内的数字，或者 nums[i] 已经等于 i + 1（即已经在正确的位置了），或者它将要交换的位置上已经是正确的数字了（nums[i] == nums[nums[i] - 1]，为了避免死循环）。

2. 查找缺失的数字

   • 经过上一步的“归位”操作后，理想情况下，数组中如果存在 1, 2, 3... 这些数字，它们会被放在 nums[0], nums[1], nums[2]... 的位置。

   • 我们再次从头遍历数组，查找第一个不满足 nums[i] == i + 1 的位置。

   • 如果找到了这样的 i，那么 i + 1 就是我们寻找的那个“没有出现的最小正整数”。

   • 如果整个数组都满足 nums[i] == i + 1，那就说明 1, 2, ..., n 这 n 个数字都齐全了，那么缺失的最小正整数就是 n + 1。

这个算法的精妙之处在于，虽然有嵌套循环，但每个数字最多被交换到其正确位置一次，所以总的时间复杂度依然是 O(n)。

class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n = nums.size();// 步骤 1: 原地哈希，将数字放到对应的索引位置// 例如，数字 1 应该在索引 0，数字 3 应该在索引 2for (int i = 0; i < n; ++i) {// 当 nums[i] 在 [1, n] 范围内，并且没有在正确的位置上时，// 就把它换到正确的位置上。// nums[i] != nums[nums[i] - 1] 是为了防止要交换的两个数相等，从而陷入死循环while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {swap(nums[i], nums[nums[i] - 1]);}}// 步骤 2: 查找第一个不满足 nums[i] == i + 1 的位置// 这个位置对应的数字 i + 1 就是缺失的最小正整数for (int i = 0; i < n; ++i) {if (nums[i] != i + 1) {return i + 1;}}// 如果 1 到 n 都存在，那么缺失的最小正整数就是 n + 1return n + 1;}
};