找出数字序列的差距

Question

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

我想要一个简单的方法来查看这个向量并说"给我最低数字> = 1,它不会出现在向量中".所以,

对于上面三个例子,答案分别是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;
}

Answer 2

选中的答案使用<进行比较.!=更简单:

int find_gap(std::vector<int> vec) {
    std::sort(vec.begin(), vec.end());
    int next = 1;
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        if (*it != next) return next;
       ++next;
    }
    return next;
}

find_gap(1,2,4,5) = 3
find_gap(2) = 1
find_gap(1,2,3) = 4

我没有传递对向量的引用,因为a)他说时间无关紧要b)所以我不改变原始向量的顺序.

Answer 3

对列表进行排序然后进行线性搜索似乎是最简单的解决方案。根据列表的预期组成，您可以使用不太通用的排序算法，如果您自己实现排序，则可以在排序期间跟踪数据，这些数据可用于加速（或完全消除）搜索步骤。我认为这个问题没有任何特别优雅的解决方案