41. 缺失的第一个正整数

1. 题目简介

难度：困难，原题链接：41. 缺失的第一个正整数。

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

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

2. 问题分析

长度为 n 的数组，缺失的第一个正整数一定在 [1, n + 1] 内。如果 1 到 n 都出现了，答案就是 n + 1；否则，答案就在 1 到 n 中。因此，非正数和大于 n 的数字都不需要占据专门的标记位置。

可以直接用原数组的下标记录出现情况：把数字 t 放到下标 t - 1，例如把 1 放到下标 0，把 3 放到下标 2。这样，最后从左往右检查，第一个不满足 nums[i] == i + 1 的位置，就说明缺少数字 i + 1。

遍历到 nums[i] 时，只要它在 [1, n] 内，就尝试把它交换到对应位置。交换回来的是另一个数字，因此还要继续检查当前位置，直到当前数字已经归位、超出范围，或目标位置已经保存了相同数字。

最后一种情况是为了处理重复值。例如 [1, 1] 中，第二个 1 的目标位置已经是 1，再交换也不会改变数组。如果不停止，就会陷入死循环。

3. 代码实现

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        // 第一次遍历：将数字放到理想位置
        for (int i = 0; i < n; i++) {
            // 当前数字在 1~n 之间且不在理想位置时进行交换
            while (nums[i] != i + 1 && nums[i] > 0 && nums[i] <= n) {
                int swap = nums[i];
                // 避免重复数字导致的死循环
                if (nums[swap - 1] == swap) {
                    break;
                }
                nums[i] = nums[swap - 1];
                nums[swap - 1] = swap;
            }
        }

        // 第二次遍历：找到第一个不在理想位置的数字
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

4. 复杂度分析

• 时间复杂度：O(n)。虽然有嵌套循环，但每次有效交换都会让一个数字归位，已经归位的数字不会再被移走，因此交换总次数不超过 n。最后再扫描一次查找答案。
• 空间复杂度：O(1)，只用少量变量完成交换。

5. 其他

我在面试微软时遇到过这道题，五轮面试中有两位面试官分别问到了它。

来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明