问题描述
LeetCode 41. 缺失的第一个正数 (opens in a new tab)，难度困难。
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1
输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。
示例 2
输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。
示例 3
输入：nums = [7,8,9,11,12] 输出：1 解释：最小的正数 1 没有出现。
提示：
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1
题解
排序
解题思路：先排序，然后遍历排序后的数组，如果存在 nums[i] == result，则递增 result 。虽然过了用例，但时间复杂度 没有满足题意。
Solution.java
class Solution {
public int firstMissingPositive(int[] nums) {
int result = 1;
Arrays.sort(nums);
for (int i = 0; i < nums.length; ++i) {
if (nums[i] == result) {
result++;
}
}
return result;
}
}原地哈希
解题思路：利用数组索引的有序性，通过将数组本身视为哈希表，将数组索引作为键，修改数组中的值来记录是否存在某个数字。
- 将所有不在
[1, n]范围内的数字替换为n + 1。因为我们只关心[1, n]范围内的数字，超出这个范围的数字对找出第一个缺失的正数没有影响； - 遍历数组，将数组中每个元素
num = nums[i]存放在对应的索引为num - 1并将该位置的值变为负数，表示数字num出现过； - 再次遍历数组，存在
nums[i] > 0即i表示i + 1这个数字缺失（因为刚刚计算索引的时候num - 1）； - 如果数组中的所有位置都被正确标记，则返回
n + 1。
具体代码如下，关键代码已写注解。
Solution.java
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// 将不在范围 [1, n] 内的所有数字替换为 n + 1
for (int i = 0; i < n; ++i) {
if (nums[i] <= 0 || nums[i] > n) {
nums[i] = n + 1;
}
}
// 使用索引作为哈希键，使用数字的符号作为存在检测器
for (int i = 0; i < n; ++i) {
// nums[num] = -nums[num] 会将 num 转换为负数，又因为索引的 >= 0，所以需要取绝对值
// 比如
int num = Math.abs(nums[i]);
if (num > n) {
continue;
}
num--; // num 的范围是 [1, n]，因为数组索引是从 0 开始的，所以需要将 num 减 1
if (nums[num] > 0) {
// nums[num] < 0 表示索引 num + 1 这个数存在
// 因为 num + 1 存在，对应 nums[num] 才能取反小于 0
nums[num] = -nums[num];
}
}
// 第一个正数索引 + 1 是缺失数字
// 在范围 [1, n] 内，如果存在 nums[i] > 0，说明 i + 1 不存在，即就是我们需要找的答案
for (int i = 0; i < n; i++) {
if (nums[i] > 0) {
return i + 1;
}
}
// 如果 1 到 n 的所有数字都存在，则返回 n + 1
return n + 1;
}
}