哈希表题目：缺失的第一个正数网站首页 技术杂谈

哈希表题目：缺失的第一个正数

伟大的车尔尼 2023-07-14 00:00:02

简介哈希表题目：缺失的第一个正数

文章目录

题目
解法

题目

标题和出处

标题：缺失的第一个正数

出处：41. 缺失的第一个正数

难度

7 级

题目描述

要求

给你一个未排序的整数数组 $nums$ ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 $O(n)$ 并且只使用常数级别额外空间的解决方案。

示例

示例 1：

输入： $nums = [1,2,0]$
输出： $3$

示例 2：

输入： $nums = [3,4,-1,1]$
输出： $2$

示例 3：

输入： $nums = [7,8,9,11,12]$
输出： $1$

数据范围

$exttt{10}^ exttt{5}$
$exttt{-2}^ exttt{31} le exttt{nums[i]} le exttt{2}^ exttt{31} - exttt{1}$

解法

思路和算法

这道题要求找出数组 $nums$ 中缺失的第一个正整数。假设数组 $nums$ 的长度是 $n$ ，常规的做法是使用哈希集合存储数组中的整数，然后遍历从 $1$ 到 $n$ 的每个正整数，当遇到第一个不在哈希表中的正整数时返回该正整数，如果从 $1$ 到 $n$ 的正整数都在哈希集合中则数组的 $n$ 个元素为这 $n$ 个不同的正整数，返回 $n + 1$ 。使用哈希表的时间复杂度是 $O (n)$ ，符合题目要求，但是空间复杂度是 $O (n)$ ，不符合题目要求的常数空间。

为了将空间复杂度降低到常数，不能额外创建哈希表，只能原地修改数组。由于数组 $nums$ 的长度是 $n$ ，下标范围是 $[0, n - 1]$ ，因此可以将数组看成哈希表，利用数组下标的信息表示每个正整数是否在数组中。对于下标 $index$ ，满足 $0 \leq index < n$ ， $1 \leq index + 1 \leq n$ ， $nums [index]$ 可以用于表示正整数 $index + 1$ 是否在数组中。

由于数组中的元素可能是任意整数，不一定在范围 $[1, n]$ 内，也可能是 $0$ 、负整数或者大于 $n$ 的正整数，因此需要处理数组中的元素，使得数组中的元素都在范围 $[1, n]$ 内且不影响结果。

由于 $1$ 是最小的正整数，因此可以首先遍历数组判断 $1$ 是否在数组中，如果 $1$ 不在数组中则缺失的第一个正整数是 $1$ ，返回 $1$ ，如果 $1$ 在数组中则继续寻找缺失的第一个正整数。

当 $1$ 在数组中时，缺失的第一个正整数一定大于 $1$ ，因此可以将数组中所有的小于 $1$ 或者大于 $n$ 的元素全部改成 $1$ ，使得所有元素都在范围 $[1, n]$ 内，然后利用数组下标的信息寻找缺失的第一个正整数。

遍历数组 $nums$ 。对于元素 $num$ ，其对应的下标为 $index = ∣ num ∣ - 1$ ，如果 $nums [index] > 0$ ，则将 $nums [index]$ 的值更新为其相反数。遍历结束之后，对于 $0 \leq index < n$ ， $nums [index] < 0$ 表示正整数 $index + 1$ 在数组 $nums$ 中， $nums [index] > 0$ 表示正整数 $index + 1$ 不在数组 $nums$ 中。

再次遍历数组 $nums$ ，找到最小的满足 $nums [i] > 0$ 的下标 $i$ 并返回 $i + 1$ 。如果数组 $nums$ 中的所有元素都是负数，则 $1$ 到 $n$ 都在数组中，返回 $n + 1$ 。

上述操作对数组 $nums$ 遍历了 $4$ 次：

第 $1$ 次遍历判断 $1$ 是否在数组中；
第 $2$ 次遍历将数组中所有的小于 $1$ 或者大于 $n$ 的元素全部改成 $1$ ；
第 $3$ 次遍历将数组中的每个元素对应的下标处的元素更新为负数；
第 $4$ 次遍历寻找缺失的第一个正整数。

其实，前两次遍历可以合并为一次遍历，具体做法是使用一个标志符记录 $1$ 是否在数组中，标志符的初始值为 $false$ ，对于数组中的每个元素，如果该元素等于 $1$ 则将标志符设为 $true$ ，如果该元素小于 $1$ 或者大于 $n$ 则将该元素改成 $1$ 。该次遍历结束时，如果标志符为 $false$ 则返回 $1$ ，并不会因为数组中的部分元素被改成 $1$ 而影响结果，如果标志符为 $true$ 则继续寻找缺失的第一个正整数。

将前两次遍历合并为一次遍历之后，遍历总次数从 $4$ 次减少为 $3$ 次。

代码

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        boolean oneExists = false;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                oneExists = true;
            } else if (nums[i] < 1 || nums[i] > n) {
                nums[i] = 1;
            }
        }
        if (!oneExists) {
            return 1;
        }
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            int index = Math.abs(num) - 1;
            if (nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
}