许多答案概述了算法或提供了解决问题的代码，这非常有帮助。令人惊奇的是，许多顶级答案都是基于同一种算法洞察力的变化（本质上）。实际上，通过走过特定的推理路径，我们可以重新发明它们，以一种更能让我们理解为什么它们正确工作的方式。
让我们从一些简单的观察开始。首先，如果我们有一个包含n个项目的数组，则最小的缺失整数必须是1、2、3、...、n或n+1中的一个。原因是，如果任何1、2、3、...或n中的任何一个值不在数组中，则在该范围内缺少的最小值必须是我们想要的值。否则，如果所有值1、2、3、...和n都在数组中，则最小缺失值为n+1。
这个观点对我们很有帮助，因为它让我们重新定义了我们要寻找的内容。具体而言，我们的任务将是追踪原始数组中存在哪些数字1、2、3、...和n。如果我们能做到这一点，解决问题就相对简单了。一旦我们知道哪些项目存在，我们就可以从1、2、3、...、n开始计数，直到找到第一个缺失的数字。如果这些值中没有任何一个缺失，那么答案就是n+1。
现在，我们的目标是找出如何在使用少量时间和空间的情况下完成此操作。
让我们先采用一种比允许的更多时间和空间的方法，然后看看如何将其优化到O(n)时间和O(1)辅助空间。我们将维护一个辅助集合，以便我们可以轻松地看到数组中存在什么。然后，我们将遍历数组，并为每个值添加到集合中，对于介于1和n之间的每个值，包括1和n。然后，我们将向上计数，以查看缺失的值是哪个。以下是一些代码：
def first_missing_integer(arr):
used = set()
for i in arr:
if 1 <= i <= len(arr):
used.add(i)
for i in range(1, len(arr)):
if i not in used:
return i
return len(arr)
这个算法的速度有多快，需要占用多少空间呢？维护一个辅助集合需要 O(n) 的辅助存储空间。我们循环遍历所有 n 个项目并将它们添加到一个 set 中，这需要预计时间 O(n)。然后，我们从 1 到 n 计数，查询我们的集合，这需要预计时间 O(n)。总体而言，这意味着我们的算法使用预计的 O(n) 时间和 O(n) 的辅助存储空间。我们在两个方面都未达到目标：
- 我们希望使用 O(1) 的辅助空间，而不是 O(n) 的辅助空间。
- 我们希望运行时间为最坏情况下的 O(n)，而不是期望的 O(n)。
为了解决这些问题，让我们减少空间使用率。现在，我们正在使用一个辅助集合。但是，我们知道集合中的所有值都将是 1 到 n 之间（包括 1 和 n）的值。那么这可能会引导我们问：是否有更好的数据结构可以用来存储这个集合？
由于我们知道将存储的值的确切范围，因此在这里一个合理的选择是从哈希表切换到位向量。我们将创建一个n位的数组，初始值全部为0。每当我们看到一个适当范围内的值时，我们就会将相应的位翻转为1。这意味着我们不再需要使用哈希，空间开销降到了n个位的内存，而不是n个字的内存。它仍然是O(n)的空间复杂度，但具有更小的前导系数。很棒！
以下是此实现的示例：
def first_missing_integer(arr):
used = [False] * len(arr)
for i in arr:
if 1 <= i <= len(arr):
used[i - 1] = True
for i in range(len(arr)):
if not used[i]:
return i + 1
return len(arr)
这是我们先前方法的改进。现在我们以最坏情况下 O(n) 的时间运行，因为不需要哈希或随机性。而且我们的空间使用率已经降低：我们现在使用 n 个辅助位。但仍然需要 O(n) 的辅助内存。这还不够好。我们能解决这个问题吗？
关键在于我们只允许使用 O(1) 的辅助存储空间，而不是 O(1) 的总空间。也就是说，我们可以随意修改原始数组，只要我们在该数组之上只使用 O(1) 的内存即可。这打开了一个有趣的可能性：我们能否将数组本身用作位向量？也就是说，我们是否可以在原始数组中创造性地修改，来隐式表示此位向量，而不是分配一个次要位向量来跟踪存在的内容？
幸运的是，答案是肯定的。而且不仅如此，“是”还有很多不同的方法。实际上，这个问题的大多数顶级答案本质上都是“在数组本身内部编码位向量”的变体。
为了使这个想法起作用，我们需要一些方式来“标记”数组中的位置。具体而言，如果数字x + 1在某处存在，我们希望“标记”数组中的位置x。我们可以使用什么来标记该位置呢？那么，使用数字本身如何？我们可以随意重新排列数组中的项目。让我们使用以下系统：如果值x在数组中，则应将其放在位置x-1。然后，我们可以通过查看
arr[x - 1] == x来检查x是否存在。这种方法使用每个元素的位置隐式编码了我们的位向量。
事实证明，有一种好的方法可以做到这一点。看一下数组的第一个元素。如果该元素为0、负数或大于n + 1，则我们不需要对其进行任何操作，因为它对我们没有帮助。否则，它在1到n之间，并且需要在数组中某个位置。具体而言，如果我们正在查看的值是x，则我们希望将x放在位置x-1。这可以有两种选择。
如果位置 x - 1 上的项已经等于 x，则无需再做任何操作以将 x 放置在位置 x - 1 上。
否则，在位置 x - 1 上有其他某个项。将该项与 x 交换。然后，需要将该项放置在其他位置，因此重复此过程。
如果我们从左到右扫描数组，并根据需要移动和移动项目，那么最多只会移动每个项目一次。为什么？因为只有当一个项目被交换到它应该在的位置时，或者不在应该在的位置并被替换为另一个元素时，才会移动该项目。这意味着交换共计花费 O(n) 的时间，仅需要 O(1) 的辅助空间。（具有现代代数背景的人可能会认识到这本质上是计算部分排列元素 1、2、...、n 的
循环分解并将其反转。）
一旦我们交换了所有的东西，我们就可以使用之前的策略，从1、2、3、...一直数到n，以查看缺少哪个项目。我们不再检查位向量，而是检查原始数组中每个位置上的内容。具体如下：
def first_missing_integer(arr):
for i in range(len(arr)):
toPlace = arr[i]
while 1 <= toPlace <= len(arr) and arr[toPlace - 1] != toPlace:
arr[i], arr[toPlace - 1] = arr[toPlace - 1], arr[i]
toPlace = arr[i]
for i in range(len(arr)):
if arr[i] != i + 1:
return i + 1
return len(arr)
这种方法与Abhijit Sarkar提出的
方法、Anubis提出的
方法以及sarkar提出的
方法密切相关。由于它仅仅是对数字进行重新排列，不改变这些值的内容，因此它的优点是无论原始数字采用何种格式（例如：有符号32位整数、无符号64位整数等），都可以使用该方法。
另一方面，假设我们使用的是带符号整数（比如Java的int类型）。我们知道我们只关心1、2、3、...、n这些正数。因此，这些数字的符号位始终为0。因此，我们可以考虑“窃取”该位，并在输入数组中直接编码我们原始的位向量思想。例如，假设我们有以下输入数组：
Array: 3, 1, 4, 1, 5, 9, 2
Index: 0 1 2 3 4 5 6
我们可以扫描输入数组。当我们读取一个值x，其中1 ≤ x ≤ n时，我们将在位置x-1处的元素设置为负数，通过设置其符号位。在这种情况下，当我们完成时，它看起来像这样：
Array: -3, -1, -4, -1, -5, 9, 2
Index: 0 1 2 3 4 5 6
现在，我们只需要找到第一个非负值。该值的索引对应于位向量中未被设置的第一个位（这里是索引5），因此我们的答案将是5加1再得到6。
这里的一个复杂性在于，我们的输入数组可以包含负数，并且那些已经存在的负数可能会通过虚假地指示缺失数字而混淆这种方法。同样，数字0也会搞砸它，因为0=-0。解决这个问题的一种方法是重新排列数组中的数字，以便所有非正数（负数和零）值存储在数组的末尾，正数值放在前面。从那里开始，我们只需假装我们正在处理由正值形成的子数组即可。（这本质上就是@pmcarpan和Harlan Gray提出的方法。）编写代码需要使用原地分区算法来移动事物。幸运的是，C++有这样的算法作为其标准库的一部分，这意味着我们可以像这样编写代码：
int32_t first_missing_integer(std::vector<int32_t>& arr) {
auto boundary = std::partition(arr.begin(), arr.end(),
[](int32_t val) {
return val > 0;
});
size_t n = boundary - arr.begin();
for (int32_t elem: arr) {
int32_t value = std::abs(elem);
if (1 <= value && value <= n && arr[value] > 0) {
arr[value] *= -1;
}
}
for (int32_t i = 1; i <= n; i++) {
if (arr[i - 1] > 0) {
return i;
}
}
return n + 1;
}
希望这有所帮助！
