数组自己就是哈希表-这道Hard题的解法太惊艳了

在这里插入图片描述

求解思路

这道题我们把数组想象成一个特殊的容器,理想情况下索引 0 应该放数字 1,索引 1 应该放数字 2,以此类推。

我们用两个指针来维护三个区域:

左边是已经整理好的"完美区"(每个位置都放着正确的数字),

中间是待处理区,

右边是"垃圾区"(存放那些不可能成为答案的数字,比如负数、超大的数、重复的数)。

处理过程就像整理房间,

我们盯着待处理区的左边界,如果这个位置的数字恰好是它该在的位置,就扩大完美区;

如果这个数字是垃圾(太小、太大或重复),就把它扔到垃圾区;

如果这个数字本身没问题但放错了位置,就把它交换到它应该去的地方。

这样不断循环,当完美区和垃圾区碰头时,完美区的长度加 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


public static int firstMissingPositive(int[] arr) {
    int l = 0;  // 左指针,左边是完美区 [0...l-1]
    int r = arr.length;  // 右指针,右边是垃圾区 [r...n-1]
    
    while (l < r) {
        if (arr[l] == l + 1) {
            // 当前位置数字正确,扩大完美区
            l++;
        } else if (arr[l] <= l || arr[l] > r || arr[arr[l] - 1] == arr[l]) {
            // 垃圾数字:太小、太大或目标位置已有相同数字
            swap(arr, l, --r);
        } else {
            // 将数字交换到它应该在的位置
            swap(arr, l, arr[l] - 1);
        }
    }
    return l + 1;  // 完美区长度+1就是答案
}

public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

举个栗子

假设输入数组为 [3, 4, -1, 1]:

初始:l=0, r=4, arr=[3,4,-1,1]
arr[0]=3,交换到索引2:arr=[−1,4,3,1]
arr[0]=-1是垃圾,扔到垃圾区:arr=[1,4,3,−1], l=0, r=3
arr[0]=1正确,l++:l=1
arr[1]=4>r=3,是垃圾:arr=[1,3,4,−1], l=1, r=2
arr[1]=3>r=2,是垃圾:arr=[1,3,4,−1], l=1, r=1
退出循环,返回 l+1=2

答案是 2,因为数组中有 1 但没有 2。

如果觉得有帮助，欢迎点赞、关注、转发~