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

Question

这个问题之前已经被问过, 但我找不到C++的答案。

如果我有一个向量和一个起始数字，是否std::algorithm提供了一种方法来查找下一个最高的缺失数字？

我显然可以在嵌套循环中编写此代码，但我无法摆脱重复发明轮子的感觉。

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

起始数字0应该找到2。
起始数字6应该找到9。
起始数字-2应该找到-1。

编辑：

到目前为止，所有解决方案都需要排序。实际上可能需要这样做，但必须创建一个临时排序的vector来容纳此操作，因为foo必须保持不变。

- Jonathan Mee

---

来到这里希望找到一个优雅的STL解决方案，只需使用一两行代码。但似乎这种解决方案不存在 - 有点难过 :-) - dhaumann

@dhaumann，是的，我认为我的代码是这里最简单的，但我仍然觉得它需要被封装成一个函数。如果你的向量可以排序，那么你肯定可以简化代码。如果你在这里提出一个有序向量的问题并将链接发给我，我会提供一个只需两行STL代码的解决方案。 - Jonathan Mee

@dhaumann 其实取消吧，你可以只排序，然后查看这里的已接受答案：http://stackoverflow.com/q/27861373/2642059 - Jonathan Mee

Answer 1

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

如果您想使用类似O(N log N)复杂度的算法来实现，可以先对输入进行排序。然后使用std::upper_bound查找您要求的数（如果有）。从那里开始，找到与前一个数字相差超过1的数字。从那里开始，在集合中扫描连续数字之间大于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";
}

这个做法并不像通常认为的那样是提供外部向量的最优解，因为它可以/不会保持未排序状态（也不会以任何方式修改）。我通过创建向量的副本并在find_missing函数内对副本进行排序来实现这一点。因此，原始向量保持未修改状态。缺点显而易见：如果向量很大，复制它可能会很昂贵。此外，这将导致每次查询都对向量进行排序，而不是先排序一次，然后对其执行所需的所有查询。

- Jerry Coffin

---

std::upper_bound 很有趣。但我认为比较函数无法调整到足以使其在未排序的容器上工作。我真正想要的是一些可以在不排序的情况下工作的东西，因为我不能对 vector 进行排序。 - Jonathan Mee

我不知道adjacent_difference的存在。 - bolov

@bolov：我（众多使命之一）之一是帮助让在 <numeric> 中隐藏的算法更加可见。 :-) - Jerry Coffin

我会在不久的将来尝试理解这个：))。与此同时，我编译并运行了一些测试用例，并发现对于不在容器中的数字，它会给出错误的输出：例如(elem:result) (-2:-1, 5:9, 20:21)。 - bolov

@bolov：至少我看问题的方式，那些看起来是正确的答案。 - Jerry Coffin

@bolov 我并没有明确指定如果范围是包含还是不包含的应该发生什么。我本意是排除范围。所以这是正确的结果。 - Jonathan Mee

Answer 2

所以我想发表一个答案。我不知道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;
}

- Jonathan Mee

---

+1，但是if(i - elem < range.size())真的需要改成if(i >= elem && i - elem < range.size())，否则会出现糟糕的情况。 - ruakh

@ruakh 谢谢，我在测试中漏掉了那个。 - Jonathan Mee

Answer 3

• 首先，您需要对向量进行排序。使用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;
}

结果：

-2: -2  
0: 2  
5: 5  
6: 9  
20: 20  

---

关于排序的说明：根据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;

- bolov

---

在我看来，upper_bound比lower_bound更合理。如果有多个请求的数字实例，你会想要最后一个，而不是第一个。 - Jerry Coffin

@JerryCoffin 我考虑过这个问题，但是使用upper_bound函数时无法确定元素是否在范围内。如果不在范围内，则该元素是第一个缺失的元素。 - bolov

似乎if (*result == input_number)是一种非常简单的方法，可以确定返回的迭代器是否指向输入数字或更大的数字。另外请注意，如果该数字不存在，则 lower_bound 和 upper_bound 将同时返回完全相同的结果（指向所请求项的下一个更大项的迭代器）。 - Jerry Coffin

@JerryCoffin 是的。但是如果容器中存在重复项，不管是lower_bound还是upper_bound，算法都会 彻底失败 。（会将第一个重复项作为第一个缺失项来查找）我会编辑的。 - bolov

@bolov 感谢您的解决方案！从所有答案来看，处理这个问题的唯一方法似乎是对vector进行排序，这让我感到难过，但事实就是如此。 - Jonathan Mee

@bolov 我一直试图让vector保持未排序状态，因为我需要重新编码的工作量太大了。如果我决定对其进行排序，我相信最好维护一个已排序的vector并使用这个解决方案：http://stackoverflow.com/q/27861373/2642059 - Jonathan Mee

Answer 4

第一种解决方案：

对向量进行排序。找到起始数字并查看下一个数字是什么。这将需要O（NlogN）的时间，其中N是向量的大小。

第二种解决方案：

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

- Ashot

---

我认为楼主更希望得到一些更具体的、符合C++风格的解决方案，而不仅仅是基本算法的一般描述。（但是，点赞。即使可能，也并非所有问题都适合使用STL。） - ruakh

顺便说一下，你的第二种方法可以进行调整，即使 M 不小，也可以忽略范围 [x + 1, x + N] 外的值。 - ruakh

是的，辅助内存将是O(N)而不是O(M)。 - Ashot

@Ashot 我的问题是我无法对向量进行排序，否则我只需维护一个已排序的向量并执行此操作：http://stackoverflow.com/q/27861373/2642059。我目前的解决方案是维护一个 vector<bool>。这可能是最好的解决方案了 :( - Jonathan Mee