LeetCode 刷题：041，缺失的第一个整数

二哥瞎逼逼：人生最大的牢笼其实都是自己给的，以前我觉得刷 LeetCode 没多大用，也不需要，最近写 LeetCode 刷题笔记，反而得到了一些以前不曾有的快乐，尤其是对代码的一些逻辑推敲，感觉更清晰了。

题意

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

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

难度

困难

示例

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

分析 1

我们先不考虑“时间复杂度为 O(n) 并且只使用常数级别额外空间”这个限制条件。

好，先搞清楚正数是什么？

正数是大于 0 的整数，那么我们可以直接暴力来解题。

• 获取数组的长度 n。
• 从 1 开始检查每个正整数是否存在于数组中，直到找到第一个不存在的正整数。
• 使用双重循环，外层循环遍历正整数 i，内层循环遍历数组 nums，检查 i 是否存在于数组中。
• 如果当前整数 i 不存在于数组中，返回 i。

也就是说，假如输入是 [1, 2, 0]，那么我们就从 1 开始检查，1 存在于数组中，2 也存在于数组中，3 不存在于数组中，所以返回 3。

假如输入是 [3, 4, -1, 1]，还是从 1 开始检查，1 ≠ 3,1≠4，1≠-1，1=1，好，1 存在于数组中，然后开始检查 2，很显然，2 不存在于数组中，所以返回 2。

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // 从 1 开始检查每个正整数是否存在于数组中...