【LeetCode热题100】41. 缺失的第一个正数（数组）

本文主要是介绍【LeetCode热题100】41. 缺失的第一个正数（数组），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一.题目要求

给你一个未排序的整数数组 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 <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1

四.解题思路

原地哈希
思路：长度为n的数组nums缺失的第一个正数的范围只可能是1 ~ n+1
极端情况：长度为5 数组nums为 1, 2, 3, 4, 5 即前五个数都出现，那么缺失的数就是n + 1 = 6
遍历一遍数组，将nums[i]的值映射到原本属于它的位置上，此题的映射规则为 对于数 val 映射到 nums[val - 1]
如nums[5] = 4；此时值4处在了值6应该在的位置，要把4映射到nums[3]
以此类推，把所有符合1 - n的数都映射到其对应的位置，那么在nums[i]中，某个数不是i+1，则这个数就是所求缺失值
否则表面所有数都是按照1，2，3，4的顺序映射那么不存在的最小整数就是n + 1

五.代码实现

class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n = nums.size();for (int i = 0; i < n; i++) {// 注意:// 这里while的目的是让nums[i]里的元素被最终定下来,最后留在nums[i]的元素一定要么是i + 1要么是一个不符合1 ~ n的数while (nums[i] > 0 && nums[i] <= n && nums[i] != i + 1 &&nums[nums[i] - 1] != nums[i]) {std::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;}
};