个人主页Milestone-里程碑❄️个人专栏: 力扣hot100 CLinuxGitMySQL心向往之行必能至题目描述给你一个未排序的整数数组nums请你找出其中没有出现的最小的正整数。进阶你能实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案吗示例 1输入nums [1,2,0]输出3示例 2输入nums [3,4,-1,1]输出2示例 3输入nums [7,8,9,11,12]输出1数据范围1 nums.length 5 * 10^5-2^31 nums[i] 2^31 - 1解题思路这道题是 LeetCode Hot100 中的困难级高频题核心难点在于O (n) 时间复杂度 O (1) 空间复杂度的限制常规的哈希表 / 排序方法都无法满足要求因此我们采用原地哈希的思路核心思想利用数组本身作为哈希表将数值为k的正整数放到下标为k-1的位置数字1→ 下标0数字2→ 下标1...数字n→ 下标n-1n为数组长度解题步骤原地归位遍历数组将每个有效范围内的正整数交换到正确的位置查找缺失值再次遍历数组第一个下标i对应的值不等于i1的位置i1就是缺失的最小正整数边界处理如果数组中1~n都完整存在返回n1。代码实现Ccpp运行class Solution { public: int firstMissingPositive(vectorint nums) { int n nums.size(); // 第一步将每个正整数交换到正确的位置 for (int i 0; i n; i) { // 循环交换当前数是有效正整数且不在正确位置时持续交换 while (nums[i] 1 nums[i] n nums[i] ! nums[nums[i] - 1]) { // 计算当前数应该存放的下标 int j nums[i] - 1; // 交换元素将nums[i]放到正确位置 swap(nums[i], nums[j]); } } // 第二步遍历查找第一个缺失的正整数 for (int i 0; i n; i) { if (nums[i] ! i 1) { return i 1; } } // 第三步1~n都存在返回n1 return n 1; } };代码逐行解析1. 变量定义cpp运行int n nums.size();定义数组长度n简化后续代码同时明确有效正整数的范围是[1, n]超过n的正整数不可能是答案。2. 原地归位循环cpp运行for (int i 0; i n; i) { while (nums[i] 1 nums[i] n nums[i] ! nums[nums[i] - 1]) { int j nums[i] - 1; swap(nums[i], nums[j]); } }外层for循环遍历数组每一个位置确保每个数都被归位内层while循环持续交换直到当前数归位 / 超出范围三个条件缺一不可1 nums[i] n只处理有效范围内的正整数负数、0、大于 n 的数直接忽略nums[i] ! nums[nums[i]-1]避免重复元素死循环比如两个 1 交换会无限循环swap(nums[i], nums[j])将当前数交换到它应该在的位置。3. 查找缺失值cpp运行for (int i 0; i n; i) { if (nums[i] ! i 1) { return i 1; } } return n 1;遍历归位后的数组若nums[i] ! i1说明i1是缺失的最小正整数若所有位置都正确说明1~n都存在返回n1。复杂度分析时间复杂度O(n)每个元素最多被交换1 次就能归位两层循环总操作次数是线性的。空间复杂度O(1)仅使用了常数个临时变量没有开辟额外的数组 / 哈希表完全满足题目进阶要求。测试用例验证用例[1,2,0]归位后[1,2,0]遍历发现下标 2 值≠3返回 3用例[3,4,-1,1]归位后[1,-1,3,4]遍历发现下标 1 值≠2返回 2用例[7,8,9,11,12]归位后无变化遍历发现下标 0 值≠1返回 1。总结这道题的核心是原地哈希思想通过利用数组自身存储映射关系突破了常数空间的限制是 LeetCode 高频考察的思维题。掌握这个思路后同类的「原地修改数组找缺失值」题目都可以用相同逻辑解决