查找第一个缺少的正整数

Question

给定一个整数数组，找到线性时间和常量空间中第一个缺失的正整数。换句话说，找到数组中不存在的最低正整数。数组也可以包含重复项和负数。

例如，输入 [3， 4， -1， 1] 应给出 2。输入 [1， 2， 0] 应给出 3。

我这样做了，但无法通过它，然后在谷歌上搜索它，得到了极客的极客答案，但无法理解它。任何人都可以使用简单的概念为此提供逻辑吗？我刚刚开始竞争性编程。

Answer 1

找到解决方案的一种方法是重新排列数组，然后找到第一个 数字放错地方：

int find_missing(std::vector<int>& v)
{
for (std::size_t i = 0; i != v.size(); ++i) {
std::size_t e = i;
while (0 < v[e]                      // Correct range
&& std::size_t(v[e]) <= v.size() // Correct range
&& std::size_t(v[e]) != e + 1    // Correct place
&& v[e] != v[v[e] - 1]           // Duplicate
) {
std::swap(v[e], v[v[e] - 1]);
}
}
// Now the array look like
// {1, 2, 3, x, 5, 6, x}
// Find first misplaced number
for (std::size_t i = 0; i != v.size(); ++i) {
if (std::size_t(v[i]) != i + 1) {
return i + 1;   
}
}
// All are correctly placed:
return v.size();
}

演示

Answer 2

如果位图(位掩码的扩展(是可以接受的，那么我们可以为每个正整数使用 1 位，然后滚动数组。位图初始化时所有位均为 0。当我们滚动数组时，我们忽略负数并在遇到 n 时打开第 n 位。例如，当我们找到 13 时，我们将第 13 位变为 1。(同样，数字 1 会将第一位变为 1(然后我们滚动位掩码并检查第一个零。做。

但是，这可能根本不被认为是恒定的复杂性，因为当最大正整数为 MAXINT 时，我们需要位图大于 MAXINT。太糟糕了。不过，从理论上讲，这是正确的。另外 O(2*N( = O(N(

因此，我们必须在数组中存储一些信息，否则这不可能一次性在O(N(中解决。

另一种解决方案包括将数组索引与整数映射并使用符号存储信息。例如，如果数组大小为 L，则缺少的 int 将小于或等于 L+1(当数组已满时为 L+1，例如 [1,2,3,4]，除非这种情况计为没有缺少元素(。感谢贾罗德对此的提示。

认为 O(3N( 仍然是 O(N(，怎么样：

步骤1：滚动数组并交换负数和零，将它们移动到开头。将所有非正值(以这种方式交换(转换为 1。真正的积极因素将从指数j开始。

第 2 步：整个数组现在是正数，但真实数据位于从 j 到数组末尾。使用真实数据滚动子数组，当您找到数字 H 时，将整个数组的第 H 个索引数字变为负数。如果 H 大于数组大小，请跳过它。当您找到示例 2 时，将 arr[1](第二个元素(变为负数。

步骤3：再次滚动数组，检查第一个正数。根据索引，您知道第一个缺少的正整数是什么。