c++ - 查找数字序列中的间隙

Question

我有一个 std::vector 包含一些数字，这些数字没有任何特定顺序，数字之间可能有也可能没有间隙 - 例如，我可能有 { 1,2,3, 6 }或 { 2,8,4,6 } 或 { 1, 9, 5, 2 } 等。

我想要一种简单的方法来查看此 vector 并说“给我最小的数字 >= 1，它不出现在 vector 中”。所以，

对于上面的三个例子，答案分别是 4、1 和 3。

这不是性能关键，而且列表很短，因此复制列表和排序不存在任何问题，例如。

我并不是真的想办法做到这一点，但我的 STL 技能严重萎缩，我能感觉到我将要做一些不雅的事情 - 我很想看看其他人想出了什么。

Answer 1

您要查找的标准算法是 std::adjacent_find .

下面是一个解决方案，它也使用 lambda 来使谓词干净:

int first_gap( std::vector<int> vec )
{
  // Handle the special case of an empty vector.  Return 1.
  if( vec.empty() )
    return 1;

  // Sort the vector
  std::sort( vec.begin(), vec.end() );

  // Find the first adjacent pair that differ by more than 1.
  auto i = std::adjacent_find( vec.begin(), vec.end(), [](int l, int r){return l+1<r;} );

  // Handle the special case of no gaps.  Return the last value + 1.
  if ( i == vec.end() )
    --i;

  return 1 + *i;
}