Поиск пробелов в последовательности чисел

Сортировка списка и последующий линейный поиск кажется самым простым решением. В зависимости от ожидаемого состава списков вы можете использовать менее универсальный алгоритм сортировки, и если вы реализуете сортировку самостоятельно, вы можете отслеживать данные во время сортировки, которые можно использовать для ускорения (или полного исключения) шага поиска. Я не думаю, что есть какое-то изящное решение этой проблемы.

Сортировка и поиск:

std::sort(vec.begin(), vec.end());
int lowest = 1;
for(size_t ii = 1; ii < vec.size(); ++ii)
{
    if (vec[ii - 1] + 1 < vec[ii])
    {
        lowest = (vec[ii - 1] + 1);
        break;
    }
}

/* 1, 2, ..., N case */
if (lowest == vec[0]) lowest = (*vec.back()) + 1;

Итераторы могут использоваться с таким же ясным намерением, как показано в ответе @joe_mucchiello (ред: лучше).

Вы можете выделить битовый вектор (той же длины, что и входной вектор), инициализировать его нулем, а затем отметить все встречающиеся индексы (обратите внимание, что числа, превышающие длину, можно игнорировать). Затем верните первый немаркированный индекс (или длину, если все индексы отмечены, что происходит только в том случае, если все индексы встречаются во входном векторе ровно один раз).

Это должно быть асимптотически быстрее, чем сортировка и поиск. Он будет использовать больше памяти, чем сортировка, если вам разрешено уничтожить оригинал, но меньше памяти, чем сортировка, если вы должны сохранить оригинал.

На самом деле, если вы выполните пузырьковую сортировку (вы знаете ... ту, которой вас сначала учат, а затем говорят, чтобы вы никогда больше не использовали ее ...), вы сможете обнаружить первый пробел на ранней стадии процесса сортировки, поэтому вы можете остановиться на этом. Это должно дать вам самое быстрое общее время.

В проверенном ответе для сравнения используется <. ! = намного проще:

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

Я не передаю ссылку на вектор, так как а) он сказал, что время не имеет значения и б) поэтому я не меняю порядок исходного вектора.

Хорошо, вот мои 2 цента. Предположим, у вас есть вектор длины N.

1. Если N <= 2, вы можете проверить напрямую
2. Сначала используйте min_element, чтобы получить наименьший элемент, запомните его как emin
3. Вызовите nth_element, чтобы получить элемент в N / 2, назовите его ehalf
4. Если ehalf! = Emin + N / 2 есть пробел слева, примените этот метод рекурсивно, вызывая nth_element для всего массива, но запрашивая элемент N / 4. В противном случае выполните рекурсию справа с запросом элемента 3 * N / 4.

Это должно быть немного лучше, чем предварительная сортировка.

вы могли бы пойти с чем-то вроде ....

struct InSequence
{
    int _current;   bool insequence;
    InSequence() : _current(1), insequence(true){}
    bool operator()(int x) {         
        insequence = insequence ? (x == _current) : false;  
        _current++; 
        return insequence;
    }
};

int first_not_in_sequence(std::vector<int>& v)
{
    std::sort(v.begin(), v.end());
    return 1+std::count_if (v.begin(), v.end(),InSequence());
}

Стандартный алгоритм, который вы ищете, - std :: neighbour_find.

Вот решение, которое также использует лямбда для очистки предиката:

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;
}

Возможная реализация ответа Томаса Каммейера

Я нашел подход Томаса действительно умным и полезным - так как некоторые из нас мечтают о коде, а реальная реализация кажется мне немного сложной, я хотел предоставить готовый к использованию код.

Представленное здесь решение является максимально общим:

• Не делается никаких предположений о типе контейнера или диапазона, за исключением того, что их итераторы должны соответствовать требованиям ValueSwappable и RandomAccessIterator (из-за частичной сортировки с nth_element)
• Можно использовать любой числовой тип - необходимые характеристики описаны ниже.

Еще одно улучшение, которое я думаю, заключается в том, что условие отсутствия пробелов может быть проверено на ранней стадии: поскольку мы в любом случае должны сканировать минимум, мы также можем сканировать максимум одновременно, а затем определить, содержит ли диапазон чисел вообще пробел, который стоит найти.

И последнее, но не менее важное: тот же рекурсивный подход может быть адаптирован для отсортированных диапазонов! Если вы закодируете в параметре значения шаблона, что диапазон уже отсортирован, вы можете просто пропустить частичную сортировку и сделать определение минимального / максимального элементов бесполезным.

#include <type_traits>
#include <iterator>
#include <tuple>
#include <utility>
#include <algorithm>
#include <cstddef>

// number type must be:
// * arithmetic
//   * subtractable (a - b)
//   * divisible by 2 (a / 2)
// * incrementable (++a)
// * less-than-comparable (a < b)
// * default-constructible (A{})
// * copy-constructible
// * value-constructible (A(n))
// * unsigned or number range must only contain values >0

/** Find lowest gap value in a range */
template<typename Range>
typename std::remove_reference_t<Range>::value_type
lowest_gap_value_unsorted(Range&& r)
{
    static_assert(!std::is_lvalue_reference_v<Range> && !std::is_const_v<Range>, "lowest_gap_value_unsorted requires a modifiable copy of the passed range");

    return lowest_gap_value_unsorted(std::begin(r), std::end(r), std::size(r));
}

/** Find lowest gap value in a range with specified size */
template<typename Range>
typename std::remove_reference_t<Range>::value_type
lowest_gap_value_unsorted(Range&& r, std::size_t N)
{
    static_assert(!std::is_lvalue_reference_v<Range> && !std::is_const_v<Range>, "lowest_gap_value_unsorted requires a modifiable copy of the passed range");

    return lowest_gap_value_unsorted(std::begin(r), std::end(r), N);
}

/** Find lowest gap value in an iterator range */
template<typename Iterator>
typename std::iterator_traits<Iterator>::value_type
lowest_gap_value_unsorted(Iterator first, Iterator last)
{
    return lowest_gap_value_unsorted(first, last, std::distance(first, last));
}

/** Find lowest gap value in an iterator range with specified size */

template<typename Iterator>
typename std::iterator_traits<Iterator>::value_type
lowest_gap_value(Iterator first, Iterator last, std::size_t N)
{
    typedef typename std::iterator_traits<Iterator>::value_type Number;

    if (bool empty = last == first)
        return increment(Number{});

    Iterator minElem, maxElem;
    std::tie(minElem, maxElem) = std::minmax_element(first, last);

    if (bool contains0 = !(Number{} < *minElem))
        throw std::logic_error("Number range must not contain 0");

    if (bool missing1st = increment(Number{}) < *minElem)
        return increment(Number{});

    if (bool containsNoGap = !(Number(N) < increment(*maxElem - *minElem)))
        return increment(*maxElem);

    return lowest_gap_value_unsorted_recursive(first, last, N, *minElem);
}

template<typename Iterator>
typename std::iterator_traits<Iterator>::value_type
lowest_gap_value_unsorted_recursive(Iterator first, Iterator last, std::size_t N, typename std::iterator_traits<Iterator>::value_type minValue)
{
    typedef typename std::iterator_traits<Iterator>::value_type Number;

    if (N == 1)
        return ++minValue;
    if (N == 2)
    {
        // determine greater of the 2 remaining elements
        Number maxValue = !(minValue < *first) ? *std::next(first) : *first;
        if (bool gap = ++minValue < maxValue)
            return minValue;
        else
            return ++maxValue;
    }

    Iterator medianElem = std::next(first, N / 2);
    // sort partially
    std::nth_element(first, medianElem, last);

    if (bool gapInLowerHalf = (Number(N) / 2 < *medianElem - minValue))
        return lowest_gap_value_unsorted_recursive(first, medianElem, N / 2, minValue);
    else
        return lowest_gap_value_unsorted_recursive(medianElem, last, N / 2 + N % 2, *medianElem);
};

template<typename T>
T increment(T v)
{
    return ++v;
}