小学生都能看懂的题解 | #缺失的第一个正整数#

问题说明：

我们需要在一个整数列表中找到最小的正整数，这个正整数不在列表中。列表里的数字可能是正数、负数或零，而且没有重复的数字。

例子：

• 如果列表是 [1, 0, 2]，最小的不在列表中的正整数是 3。
• 如果列表是 [-2, 3, 4, 1, 5]，最小的不在列表中的正整数是 2。
• 如果列表是 [4, 5, 6, 8, 9]，最小的不在列表中的正整数是 1。

解决方法：

我们可以用列表本身来帮助我们记住哪些数字已经出现了。因为我们需要找到最小的正整数，所以我们可以只关注列表中的正数。

1. 清理列表：
1. 首先，我们把列表中的所有正数移到列表的前面。这样我们只需要关注这些正数了。
2. 标记已有的数字：
1. 然后，对于每一个正数，我们会把它放在它“应该”在的位置上。
2. 比如，如果有一个数字是 3，我们就把它放在列表的第 3 个位置（注意这里是从 1 开始计数的）。
3. 查找第一个空缺：
1. 最后，我们从头开始检查列表，找到第一个位置上的数字不是它“应该”在的位置上的那个数字。
2. 这个位置的序号就是我们要找的那个最小的不在列表中的正整数。

代码解释：

我们用一个简单的例子来解释代码：

假设我们的列表是 [1, 2, 0]。

1. 我们先把正数移到前面，但这里已经是正数了，所以我们不需要动。
2. 接下来，我们看看数字 1 是否在它应该在的位置上。数字 1 应该在第 1 个位置上，而它正好在那里。 数字 2 是否在它应该在的位置上？数字 2 应该在第 2 个位置上，而它也正好在那里。
3. 现在，我们再从头检查列表，发现每个位置上的数字都是对的，这说明列表里有 1 和 2，但是没有 3。因此，答案就是 3。

这就是解决问题的基本思路。通过这种方式，我们不需要额外的空间来存储信息，因为我们直接在列表上做了标记，这样就节省了空间。同时，我们只需要两次遍历列表，所以时间也不会很长。

下面是代码实现

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

        // 把所有正数放到数组的前半部分，并统计正数的数量
        int positiveCount = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                nums[positiveCount++] = nums[i];
            }
        }

        // 只需要考虑正数部分
        for (int i = 0; i < positiveCount; ++i) {
            while (nums[i] > 0 && nums[i] <= positiveCount && nums[nums[i] - 1] != nums[i]) {
                // 交换到正确的位置
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }

        // 查找第一个缺失的正数
        for (int i = 0; i < positiveCount; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        // 如果所有的数都存在，则返回正数的数量 + 1
        return positiveCount + 1;
    }
}

如果这篇文章对你有帮助，请点个免费的赞👍，让它能够帮助更多的人。