本篇博客讲解LeetCode热题100道普通数组篇中的五道题 第五道:缺失的第一个正数(困难)
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;
}
}
1.将负数,0,替换为n+1变成无效数字,因为我们只关心[1,n]的正数。 2.标记已存在的正整数,对于每一个元素 `nums[i]`,我们用它的绝对值 `num` 来表示。如果num是一个有效的数字,也就是num<=n。那么将数组中索引num-1的元素下标记为负数。这一步结束后,数组中所有出现过的正整数对应的索引位置都会被标记为负数。 3.查找第一个未被标记的位置。查找第一个仍然为正数的元素。此时返回i+1。 4.如果没有找到返回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;
}
}
除了打标记以外,我们还可以使用置换的方法,将给定的数组「恢复」成下面的形式:
nums[i]
放在索引 nums[i] - 1
的位置上。通过不断交换,确保每个正整数 k
出现在索引 k-1
的位置上。i
使得 nums[i] != i + 1
,即第一个缺失的正整数是 i + 1
。nums[i] == i + 1
,则返回 n + 1
,即数组长度加一的值。复杂度分析