LeetCode41 缺失的第一个正数

发表于 | 分类于 |
字数统计: 517 | 阅读时长 ≈ 2

链接： https://leetcode.cn/problems/first-missing-positive/

题意

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

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

解法

在codetop里看到的一道字节高频面试题
和之前AILab面的那道题目很像
都是找一个缺失的数字
都是需要O(n)时间复杂度 以及常数空间
做法也是类似的
进行原地修改
这种思路有一个非正式的名称：原地哈希
原地哈希就相当于，让每个数字n都回到下标为n-1的家里。

遍历一遍，把数字放在正确的位置上
再遍历一遍找到不在的数字即可
如果所有的数字都在对的位置上的话，返回数组长度+1即可

评论中的一个精彩比喻：
一开始一部分人已经在家里了
那些没有回到家里的在外流浪，他们要么是根本就没有自己的家（数字小于等于0或者大于nums.size()），要么是自己的家被别人占领了（出现了重复）。
这些流浪汉被临时安置在下标为i的空房子里，之所以有空房子是因为房子i的主人i+1失踪了（数字i+1缺失）。
因此通过原地构建哈希让各个数字回家，我们就可以找到原始数组中重复的数字还有消失的数字。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] < n) {
                int t = nums[i] - 1;
                // 如果已经在家了 就可以处理下一个位置了
                if (nums[i] == nums[t]) break; // 用于处理[1, 1]类似的样例 否则会infinite loop
                swap(nums[i], nums[t]);
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
};