题目出处
题目描述
个人解法
思路：
1.构建新数组
2.一个萝卜一个坑思想
代码示例：（Java）
todo
复杂度分析
todo
官方解法
方法1：哈希表
思路：
代码示例：（Java）
public class Solution1 {
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;
}
}
复杂度分析
- 时间复杂度：O(N)，其中 N 是数组的长度。
- 空间复杂度：O(1)。
方法2:置换
思路：
代码示例：（Java）
public class Solution2 {
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;
}
}
复杂度分析
- 时间复杂度：O(N)，其中 N 是数组的长度。
- 空间复杂度：O(1)。
考察知识点
1.正数
2.排序
