LeetCode 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 * 105
• -231 <= nums[i] <= 231 - 1

思路

想要实现题目要求的时空限制，可以利用哈希表。

根据题目分析，我们只需要考虑在 [ 1，numsize ]范围内的数据，如果数据都不在该范围内，则应该返回 1。构建哈希表的哈希方法是：该范围内数的地址 = 数值减一，然后将该地址标记，标记方法为取负，在此之前，需要将所有小于等于0的数换为 numsize+1。

标记之后遍历数组，出现的第一个正数的下标加1便是结果。

代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>int firstMissingPositive(int *nums, int numsSize);int main()
{int size = 2;int nums[4] = {2, 1};int res = firstMissingPositive(nums, size);printf("%d", res);return 0;
}int firstMissingPositive(int *nums, int numsSize)
{for (int i = 0; i < numsSize; i++){if (nums[i] <= 0){nums[i] = numsSize + 1;}}for (int i = 0; i < numsSize; i++){int t = fabs(nums[i]);if (t < numsSize + 1 && nums[t - 1] > 0){nums[t - 1] = -nums[t - 1];}}int i;for (i = 0; i < numsSize; i++){if (nums[i] >= 0){break;}}return i + 1;
}