题目链接：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。
具体思路可以分为两步：
原地哈希（元素归位）
我们遍历整个数组，对于遍历到的当前数字 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]，为了避免死循环）。
查找缺失的数字
经过上一步的“归位”操作后，理想情况下，数组中如果存在 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 应该在索引 2
for (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 + 1
return n + 1;
}
}; 