【LeetCode】41. 缺失的第一个正数
难度 困难
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例 1: 输入: [1,2,0] 输出: 3 示例 2: 输入: [3,4,-1,1] 输出: 2 示例 3: 输入: [7,8,9,11,12] 输出: 1 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/first-missing-positive 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
提示：
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
题解一 ：直接用哈希表不满足题目内存空间要求
可以直接用给的数组存
用一种特殊标记来记录某个值是否存在
如 用第n-1个下标的数是负数 表示n存在
判断 第一个出现的正数的下标 X 则缺少的就是X+1
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
if (nums[i] <= 0) {
nums[i] = n + 1;
}
}
for (int i = 0; i < n; ++i) {
int num = Math.abs(nums[i]);
if (num <= n) {
nums[num - 1] = -Math.abs(nums[num - 1]);
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] > 0) {
return i + 1;
}
}
return n + 1;
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/first-missing-positive/solution/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。因为有负数的存在一开始 所以把相应的位置 设置成正数即可 正数要超过 n 避免和 普通数混淆 可以使用n+1
遍历时 吧正数 标志的下标设置 为负数
for (int i = 0; i < n; ++i) { int num = Math.abs(nums[i]); if (num <= n) { nums[num - 1] = -Math.abs(nums[num - 1]); }
第三次遍历 找 存在的正数 下标
题解二 ： 置换数组 如 某个位置的数为 n 就把他和下标 n-1的数置换 这样一轮下来 就能保证 每个下标下面是自己的数 遍历一轮 发现有的位置没有相应的 数 即 所缺少的 数字
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/first-missing-positive/solution/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。用while循环 一换到底
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { int temp = nums[nums[i] - 1]; nums[nums[i] - 1] = nums[i]; nums[i] = temp; }