在向量中找到第一个缺失的元素

Question

这个问题 has been asked before 但我找不到它的 C++。

如果我有一个向量并且有一个起始编号，std::algorithm 是否提供了一种方法来找到下一个最大的缺失编号？

我显然可以在嵌套循环中写这个，我就是无法摆脱我正在重新发明轮子的感觉。

例如，给定：vector foo{13,8,3,6,10,1,7,0};

起始编号0应该找到2.
起始编号 6 应该找到 9.
起始编号 -2 应该找到 -1.

编辑：

到目前为止所有的解决方案都需要排序。这实际上可能是必需的，但必须创建一个临时排序的 vector 来适应这一点，因为 foo 必须保持不变。

Answer 1

第一个解决方案：

对矢量进行排序。找到起始编号，然后查看下一个编号。这将花费 O(NlogN)，其中 N 是向量的大小。

第二种解决方案：

如果数字范围较小，例如(0,M) 您可以创建大小为 M 的布尔向量。对于初始向量的每个数字，使该索引的布尔值为真。稍后您可以通过检查布尔向量来查看下一个缺失的数字。这将花费 O(N) 时间和 O(M) 辅助内存。

Answer 2

首先你需要对向量进行排序。为此使用 std::sort。
std::lower_bound 查找大于或等于给定元素的第一个元素。（元素必须至少部分排序）
从那里开始迭代，同时你有连续的元素。
处理重复项：一种方法是我采用的方法：迭代时考虑连续且相等的元素。另一种方法是添加矢量/范围包含唯一元素的先决条件。我选择前者是因为它避免了擦除元素。

以下是从排序向量中消除重复项的方法：

v.erase(std::unique(v.begin(), v.end()), v.end());

我的实现：

// finds the first missing element in the vector v
// prerequisite: v must be sorted
auto firstMissing(std::vector<int> const &v, int elem) -> int {
  auto low = std::lower_bound(std::begin(v), std::end(v), elem);

  if (low == std::end(v) || *low != elem) {
    return elem;
  }

  while (low + 1 != std::end(v) &&
         (*low == *(low + 1) || *low + 1 == *(low + 1))) {
    ++low;
  }
  return *low + 1;
}

以及通用版本：

// finds the first missing element in the range [first, last)
// prerequisite: the range must be sorted
template <class It, class T = decltype(*std::declval<It>())>
auto firstMissing(It first, It last, T elem) -> T {
  auto low = std::lower_bound(first, last, elem);

  if (low == last || *low != elem) {
    return elem;
  }

  while (std::next(low) != last &&
         (*low == *std::next(low) || *low + 1 == *std::next(low))) {
    std::advance(low, 1);
  }
  return *low + 1;
}

测试用例：

int main() {
  auto v = std::vector<int>{13, 8, 3, 6, 10, 1, 7, 7, 7, 0};    
  std::sort(v.begin(), v.end());

  for (auto n : {-2, 0, 5, 6, 20}) {
    cout << n << ": " << firstMissing(v, n) << endl;
  }

  return 0;
}

结果：

关于排序的说明：根据 OP 的评论，他正在寻找不会修改向量的解决方案。

您必须对向量进行排序以获得有效的解决方案。如果修改矢量不是一个选项，您可以创建一个副本并对其进行处理。

如果你执意不排序，有一个蛮力解决方案（非常非常低效 - O(n^2)）：

auto max = std::max_element(std::begin(v), std::end(v));
if (elem > *max) {
  return elem;
}
auto i = elem;
while (std::find(std::begin(v), std::end(v), i) != std::end(v)) {
  ++i;
}
return i;

Answer 3

至少据我所知，没有标准算法可以直接实现您的要求。

如果你想用类似 O(N log N) 的复杂度来做到这一点，你可以从对输入进行排序开始。然后使用 std::upper_bound 查找您要求的号码（如果存在）的（最后一个实例）。从那里，您会发现一个数字与之前的数字相差不止一个。从那里您将扫描集合中连续数字之间大于 1 的差异。

在实际代码中执行此操作的一种方法如下所示：

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <iterator>

int find_missing(std::vector<int> x, int number) {
    std::sort(x.begin(), x.end());
    auto pos = std::upper_bound(x.begin(), x.end(), number);

    if (*pos - number > 1)
        return number + 1;
    else {
        std::vector<int> diffs;
        std::adjacent_difference(pos, x.end(), std::back_inserter(diffs));
        auto pos2 = std::find_if(diffs.begin() + 1, diffs.end(), [](int x) { return x > 1; });
        return *(pos + (pos2 - diffs.begin() - 1)) + 1;
    }
}

int main() {
    std::vector<int> x{ 13, 8, 3, 6, 10, 1,7, 0};

    std::cout << find_missing(x, 0) << "\n";
    std::cout << find_missing(x, 6) << "\n";
}

这比您通常认为提供 can/does 保持未排序（且未以任何方式修改）的矢量外观的最佳方式要少一些。我已经通过创建向量的副本并在 find_missing 函数内对副本进行排序来完成此操作。因此，原始向量保持不变。缺点很明显：如果向量很大，复制它 can/will 会很昂贵。此外，这最终会为每个查询对向量进行排序，而不是排序一次，然后根据需要对其执行尽可能多的查询。

Answer 4

所以我想我会 post 一个答案。我不知道 std::algorithm 中有什么可以直接完成此操作，但结合 vector<bool> 你可以在 O(2N) 中完成此操作。

template <typename T>
T find_missing(const vector<T>& v, T elem){
    vector<bool> range(v.size());
    elem++;

    for_each(v.begin(), v.end(), [&](const T& i){if((i >= elem && i - elem < range.size())range[i - elem] = true;});

    auto result = distance(range.begin(), find(range.begin(), range.end(), false));

    return result + elem;
}

在向量中找到第一个缺失的元素

Find First Missing Element in a vector

c++

algorithm

vector

counting

missing-data