问题来自Codility编程培训，听起来像是：我们有一个数组（A[]），其中包含n个元素（范围从1到100,000），这些是我们的参数。数组的元素是从−2,147,483,648到2,147,483,647的整数，我们需要找到不在数组中的最小正整数。当然，这可以在O（n * logn）中轻松完成，方法是将它们全部排序并遍历排序后的数组，寻找丢失的正数（在我的解决方案中，最后一个操作的时间复杂度为O（n））。但是根据Codility，整个问题都可以在O（n）中完成，而我看不到任何解决方法。有人可以给我一些提示让我摆脱困境吗？
根据信鸽原理，数字1、2，…，n + 1中的至少一个不在数组中。让我们创建一个b大小为n + 1 的布尔数组，以存储是否存在这些数字。
b
现在，我们处理输入数组。如果找到1到n +1之间的数字，则在中标记相应的条目b。如果我们看到的数字不适合这些范围，则将其丢弃并继续下一个。两种情况的每个输入项均为O（1），总计为O（n）。
处理完输入后，我们可以b在O（n）中轻松找到布尔数组中的第一个未标记条目。
