本篇博客讲解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
复杂度分析
时间复杂度:O(N),其中 N 是数组的长度。
空间复杂度:O(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
,即数组长度加一的值。
复杂度分析
时间复杂度:O(N),其中 N 是数组的长度。
空间复杂度:O(1)。