本篇博客讲解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)。