题目描述

给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。要求时间复杂度 O(n) 且只使用常数级别额外空间。

解题思路

这是一道经典的原地哈希题目。由于要求 O(n) 时间复杂度和 O(1) 额外空间，我们需要在原数组上进行操作。

核心思路是将数组视为一个”哈希表”，让每个正整数尽可能地放在它对应的索引位置上（即值 x 应该放在下标 x - 1 的位置）。如果数组中存在 1，那么 1 应该在下标 0 的位置；存在 2，那么 2 应该在下标 1 的位置，以此类推。

具体步骤分为三趟遍历：

第一趟：将数组中所有非正整数（≤ 0）替换为 len + 1（一个超出有效范围的值）。这是为了后续处理时，只关注正整数的范围，负数和其他非正整数不会干扰标记过程。

第二趟：使用数组的索引作为标记位。遍历数组，对于每个元素的绝对值 cur，如果它在有效范围 [1, len] 内，我们就将该值对应下标 cur - 1 处的元素标记为负数（取反）。这表示数字 cur 在数组中出现过。注意需要使用绝对值处理可能已被标记为负数的元素。

第三趟：遍历数组，找到第一个值大于 0 的下标 i，说明 i + 1 这个正整数没有出现过，即为答案。如果所有位置都被标记为负（即 1 到 len 都出现了），则返回 len + 1。

这种原地标记法的精妙之处在于，利用正负号作为布尔标记，不需要额外空间。

复杂度分析

  • 时间复杂度：O(n)，遍历了三次数组，每次都是 O(n)。
  • 空间复杂度：O(1)，只使用了几个变量，没有使用额外的数据结构。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
package code.J41;

import java.util.*;

public class J41 {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] <= 0) {
                nums[i] = len + 1;
            }
        }
        for (int num : nums) {
            int cur = Math.abs(num);
            if (cur <= len) {
                nums[cur - 1] = -Math.abs(nums[cur - 1]);
            }
        }
        for (int i = 0; i < len; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return len + 1;
    }
}