数组 A 的索引从1开始。我们称一个值为活跃的值，当它不为零且不超过 n 时。
扫描数组直到找到一个活跃值，令 A[i] = k （如果找不到，则停止）;
当 A[k] 是活跃的时,
A[k] 移动到 k 的位置，并清除 A[k]；从 i 继续扫描数组，直到到达数组末尾。
这样一遍扫描后，数组中与某些整数对应的所有元素都被清除了。
例如:
[5, 3, 2, 7], clear A[3]
[5, 3, 0, 7], clear A[2]
[5, 0, 0, 7], done
1。[5, 3, 2, 7, 1], clear A[5],
[5, 3, 2, 7, 0], clear A[1]
[0, 3, 2, 7, 0], clear A[3],
[0, 3, 0, 7, 0], clear A[2],
[0, 0, 0, 7, 0], done
答案是4。
第一遍循环是线性的，因为每个数字只被查看一次（并立即清除），而i会逐渐增加。
第二遍循环是线性搜索。
A= [5, 3, 2, 7, 1]
N= len(A)
print(A)
for i in range(N):
k= A[i]
while k > 0 and k <= N:
A[k-1], k = 0, A[k-1] # -1 for 0-based indexing
print(A)
[5, 3, 2, 7, 1]
[5, 3, 2, 7, 0]
[0, 3, 2, 7, 0]
[0, 3, 2, 7, 0]
[0, 3, 0, 7, 0]
[0, 0, 0, 7, 0]
[0, 0, 0, 7, 0]
更新：
根据גלעד ברקן的想法，我们可以以不破坏值的方式标记数组元素。然后报告第一个未标记的索引。
print(A)
for a in A:
a= abs(a)
if a <= N:
A[a-1]= - A[a-1] # -1 for 0-based indexing
print(A)
[5, 3, 2, 7, 1]
[5, 3, 2, 7, -1]
[5, 3, -2, 7, -1]
[5, -3, -2, 7, -1]
[5, -3, -2, 7, -1]
[-5, -3, -2, 7, -1]
根据问题描述：“允许将数组中的值赋给其他整数。” 这是O(n)空间，而不是常量。
循环遍历数组，并将对于|A[i]| < 数组长度的元素，将其对应的A[ |A[i]| - 1 ]乘以-1。第二次循环并输出第一个未标记为负数的单元格的索引+1，如果它们全部被标记，则输出（数组长度+1）。这利用了事实上数组中不能有超过（数组长度）个不同的整数。
firstMissing
self size to: 1 by: -1 do: [:i |
[(self at: i) < i] whileTrue: [self swap: i with: (self at: i)]].
1 to: self size do: [:i |
(self at: i) = i ifFalse: [^i]].
^self size + 1
所以我们有两个O(n)的循环，但是第一个循环内部还有另一个循环(whileTrue:)。那么第一个循环真的是O(n)吗？
是的，因为每个元素最多只会交换一次，因为它们将到达它们正确的位置。我们可以看到交换的累积数量受到数组大小的限制，第一个循环的总成本最多为2*n，包括最后一个搜索的总成本最多为3*n，仍然是O(n)。
您还可以看到，我们不关心 (self at: i) > i and: [(self at:i) <= self size] 的情况下进行交换，为什么？因为我们确信在这种情况下会有一个更小的缺失元素。
一个小的测试案例：
| trial |
trial := (1 to: 100100) asArray shuffled first: 100000.
self assert: trial copy firstMissing = trial sorted firstMissing.
(self at: i) < i 时才交换索引 i 和 self at: i 的位置。因此，我从未超出 self size（在 Smalltalk 中将会导致异常的缓冲区溢出）。 - aka.nice使用这个简单而有效的算法：
A is [5, 3, 2, 7]
1- Define B With Length = A.Length; (O(1))
2- initialize B Cells With 1; (O(n))
3- For Each Item In A:
if (B.Length <= item) then B[Item] = -1 (O(n))
4- The answer is smallest index in B such that B[index] != -1 (O(n))
我差不多自己找到了正确的方法，但还是不得不搜索一下，最后在这里找到了：https://www.geeksforgeeks.org/find-the-smallest-positive-number-missing-from-an-unsorted-array/
注意：此方法会破坏原始数据
原问题中没有说明不能破坏数据。
现在我将解释您需要做什么。
基本的“aha”是，第一个缺失的数字必须出现在前N个正数中，其中N是数组的长度。
一旦您理解了这一点，并意识到可以使用数组本身的值作为标记，您只需要解决一个问题：数组中是否有小于1的数字？如果有，我们需要处理它们。
处理0或负数可以在O(n)时间内完成。获取两个整数，一个用于当前值，另一个用于数组的末尾。当我们扫描时，如果发现0或负数，我们使用第三个整数与数组中的最终值进行交换。然后我们递减数组指针的末尾。我们继续执行，直到当前指针超过数组指针的末尾。while (list[end] < 1) {
end--;
}
while (cur< end) {
if (n < 1) {
swap(list[cur], list[end]);
while (list[end] < 1) {
end--;
}
}
}
for (cur = 0; cur <= end; begin++) {
if (!(abs(list[cur]) > end)) {
list[abs(list[cur]) - 1] *= -1;
}
}
现在，请注意：您需要读取位置中整数的绝对值，因为它可能会变成负数。还要注意，如果一个整数大于您的列表结束指针，则不要更改任何内容，因为该整数将无关紧要。
最后，一旦您读取了所有正值，请遍历它们以找到当前为正的第一个数字。这个位置代表您的第一个缺失的数字。
Step 1: Segregate 0 and negative numbers from your list to the right. O(n)
Step 2: Using the end of list pointer iterate through the entire list marking
relevant positions negative. O(n-k)
Step 3: Scan the numbers for the position of the first non-negative number. O(n-k)
Space Complexity: The original list is not counted, I used 3 integers beyond that. So
it is O(1)
需要提到的一件事是，列表 [5, 4, 2, 1, 3] 最终会变成 [-5, -4, -2, -1, -3]，因此在这种情况下，您应该选择列表结束位置后的第一个数字，即6作为结果。
步骤3的代码示例：
for (cur = 0; cur < end; cur++) {
if (list[cur] > 0) {
break;
}
}
print(cur);
你可以按照以下步骤进行操作。
然而，这可能不是线性时间，我不确定。
编辑：你应该使用候选值加上输入大小的一半作为枢轴来减少常数因子 - 请参见Daniel Schepler的评论 - 但我还没有时间在示例代码中实现它。
这并不是最优解 - 正在寻找一个聪明的解决方案 - 但已足以满足标准 :)
我认为这样可以行得通...？
'use strict';
const swap = (arr, i, j) => {
[arr[i], arr[j]] = [arr[j], arr[i]];
};
// dummy pivot selection, because this part isn’t important
const selectPivot = (arr, start, end) =>
start + Math.floor(Math.random() * (end - start));
const partition = (arr, start, end) => {
let mid = selectPivot(arr, start, end);
const pivot = arr[mid];
swap(arr, mid, start);
mid = start;
for (let i = start + 1; i < end; i++) {
if (arr[i] < pivot) {
mid++;
swap(arr, i, mid);
}
}
swap(arr, mid, start);
return mid;
};
const findMissing = arr => {
let candidate = 1;
let start = 0;
let end = arr.length;
for (;;) {
if (start === end) {
return candidate;
}
const pivotIndex = partition(arr, start, end);
const pivot = arr[pivotIndex];
if (pivotIndex + 1 < pivot) {
end = pivotIndex;
} else {
//assert(pivotIndex + 1 === pivot);
candidate = pivot + 1;
start = pivotIndex + 1;
}
}
};
const createTestCase = (size, max) => {
if (max < size) {
throw new Error('size must be < max');
}
const arr = Array.from({length: max}, (_, i) => i + 1);
const expectedIndex = Math.floor(Math.random() * size);
arr.splice(expectedIndex, 1 + Math.floor(Math.random() * (max - size - 1)));
for (let i = 0; i < size; i++) {
let j = i + Math.floor(Math.random() * (size - i));
swap(arr, i, j);
}
return {
input: arr.slice(0, size),
expected: expectedIndex + 1,
};
};
for (let i = 0; i < 5; i++) {
const test = createTestCase(1000, 1024);
console.log(findMissing(test.input), test.expected);
}