☆打卡算法☆LeetCode 41、缺失的第一个正数 算法解析
☆打卡算法☆LeetCode 41、缺失的第一个正数 算法解析
恬静的小魔龙
发布于 2022-08-07 10:00:30
发布于 2022-08-07 10:00:30
一、题目
1、算法题目
“找到数组中，没有出现过的最小正整数。”
题目链接：
来源：力扣（LeetCode）
链接：41. 缺失的第一个正数 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入： nums = [1,2,0]
输出： 3示例 2：
输入： nums = [3,4,-1,1]
输出： 2二、解题
1、思路分析
这道题需要找到数组中不存在最小正整数，这个还是很容易实现的。
第一种方法用哈希表，将数组中所有的数字存到哈希表中，然后从1开始枚举正整数，判断是否在数组中，时间复杂度O(N)，空间复杂度O(N)。
第二种方法遍历枚举，从1开始枚举正整数，然后遍历数组，判断这个数字是否在数组中，时间复杂度O(N2)，空间复杂度O(1)。
但是，题目要求是时间复杂度O(N)，空间复杂度O(1)，解题容易，但是满足题意还是很难的。
只能修改算法，利用数组中的空间来存储一些状态。
2、代码实现
代码参考：
public class Solution
{
public int FirstMissingPositive(int[] nums)
{
for (int i = 0; i < nums.Length; i++)
{
while(nums[i]>0&&nums[i]<=nums.Length
&& nums[i] != nums[nums[i] - 1])
{
var next = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = next;
}
}
for (int i = 0; i < nums.Length; i++)
{
if (nums[i] != i + 1)
{
return i + 1;
}
}
return nums.Length + 1;
}
public int FirstMissingPositive1(int[] nums)
{
var add = 0;
for (int i = 0; i < nums.Length; i++)
{
while (nums[i] >= 0 && nums[i] < nums.Length
&& nums[i] != nums[nums[i]])
{
var temp = nums[nums[i]];
nums[nums[i]] = nums[i];
nums[i] = temp;
}
if (nums[i] == nums.Length)
{
add = 1;
}
}
for (int i = 1; i < nums.Length; i++)
{
if (nums[i] != i)
{
return i;
}
}
return add + nums.Length;
}
}
image.png
3、时间复杂度
时间复杂度 ： O(N)
其中 N 是数组的长度。
空间复杂度： O(1)
只需要常数级别的空间存放变量。
三、总结
本题的难点在：只能使用常数级别的额外空间，在这个限制下本题的思路有一个非正式的名称：原地哈希。
就是将数组视为哈希表，这个思路就相当于我们自己编写哈希表。
哈希表的规则很简单，那就是数值为i的数映射到下标为i-1的位置。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-11-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
