一、题目
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; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(N)
其中 N 是数组的长度。
空间复杂度： O(1)
只需要常数级别的空间存放变量。
三、总结
本题的难点在：只能使用常数级别的额外空间，在这个限制下本题的思路有一个非正式的名称：原地哈希。
就是将数组视为哈希表，这个思路就相当于我们自己编写哈希表。
哈希表的规则很简单，那就是数值为i的数映射到下标为i-1的位置。
