一【题目类别】

哈希表

二【题目难度】

困难

三【题目编号】

41.缺失的第一个正数

四【题目描述】

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

七【解题思路】

对数组中的元素进行“原地哈希”，第i个元素映射到i-1的位置
这样，对于1-N中的元素，如果没有空缺，那么缺失的第一个正数一定是N+1；如果有空缺，那么缺失的第一个整数一定在1-N中
然后我们遍历数组，对于映射不匹配的元素直接返回即可

八【时间频度】

时间复杂度： $O (n)$ ， $n$ 为传入的数组的长度
空间复杂度： $O (1)$

九【代码实现】

Java语言版

class Solution {public int firstMissingPositive(int[] nums) {int n = nums.length;for(int i = 0;i < n;i++){while(0 < nums[i] && nums[i] <= n && nums[nums[i] - 1] != nums[i]){swap(nums, nums[i] - 1, i);}}for(int i = 0;i < n;i++){if(nums[i] != i + 1){return i + 1;}}return n + 1;}public void swap(int[] nums, int index1, int index2){int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}
}

C语言版

void swap(int* nums, int index1, int index2)
{int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;
}int firstMissingPositive(int* nums, int numsSize)
{int n = numsSize;for(int i = 0;i < n;i++){while(0 < nums[i] && nums[i] <= n && nums[nums[i] - 1] != nums[i]){swap(nums, nums[i] - 1, i);}}for(int i = 0;i < n;i++){if(i + 1 != nums[i]){return i + 1;}}return n + 1;
}

Python语言版

class Solution:def firstMissingPositive(self, nums: List[int]) -> int:n = len(nums)for i in range(0, n):while 1 <= nums[i] and nums[i] <= n and nums[nums[i] - 1] != nums[i]:self.swap(nums, nums[i] - 1, i)for i in range(0, n):if nums[i] != i + 1:return i + 1return n + 1def swap(self, nums, index1, index2):temp = nums[index1]nums[index1] = nums[index2]nums[index2] = temp

C++语言版

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