当前位置 博文首页 > 知北行的博客：算法---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
提示：
0 <= nums.length <= 300
-231 <= nums[i] <= 231 - 1
Related Topics 数组
👍 1060 👎 0
class Solution {
public int firstMissingPositive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
set.add(nums[i]);
}
for (int i = 1; i <= nums.length; i++) {
if (!set.contains(i)) {
return i;
}
}
return nums.length + 1;
}
}
每个数组下标位置 i , 存放元素 i+1 , 最后遍历数组, 哪个值不在正确位置上, 即返回, 流程:
注意:
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]) {
int index = nums[i] - 1;
int temp = nums[i];
nums[i] = nums[index];
nums[index] = temp;
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return nums.length + 1;
}
}
cs参考: 原地哈希（哈希函数为：f(nums[i]) = nums[i] - 1）
