Найти первый пропущенный элемент в векторе

Question

Этот вопрос has been asked before, но я не могу найти его для C++.

Если у меня есть вектор, и у меня есть начальный номер, то std :: algorithm предоставит мне способ найти следующий самый высокий недостающий номер?

Я могу, очевидно, написать это в вложенном цикле, я просто не могу поколебать ощущение, что я изобретаю колесо.

Например, если: vector foo{13,8,3,6,10,1,7,0};

Отправной номер 0 должен найти 2.
Стартовый номер 6 должен найти 9.
Стартовый номер -2 должен найти -1.

EDIT:

До сих пор все решения требуют сортировки. На самом деле это может потребоваться, но временный отсортированный vector должен быть создан для его размещения, поскольку foo должен оставаться неизменным.

Answer 1

Так что я думал, что отправлю ответ. Я ничего не знаю в std :: алгоритме, который выполняет это напрямую, но в сочетании с 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; 
} 

Answer 2

Первое решение:

Сортировка вектора. Найдите начальный номер и посмотрите, какой номер следующий. Это займет O (NlogN), где N - размер вектора.

Второе решение:

Если диапазон чисел мал, например, (0, M) вы можете создать логический вектор размера M. Для каждого числа начального вектора булево значение этого индекса истинно. Позже вы можете увидеть следующее недостающее число, проверив булев вектор. Это займет O (N) время и O (M) вспомогательная память.

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 

---

Примечание о сортировке: Из комментариев ор, он искал решение, которое не будет изменять вектор.

Вы должны отсортировать векторное изображение для эффективного решения. Если изменение вектора не является вариантом, вы можете создать копию и работать над ней. не

Если вы одержимы не сортировка, есть решение перебора (очень неэффективно - 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 4

По крайней мере, насколько я знаю, там нет стандартный алгоритм, который непосредственно реализует именно то, о чем вы просите.

Если вы хотите сделать что-то вроде сложности 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"; 
} 

Это несколько меньше, чем вы обычно думаете, как оптимально обеспечить внешний вид вектора, который может/остается не отсортированным (и не измененным каким-либо образом). Я сделал это, создав копию вектора и отсортировав копию внутри функции find_missing. Таким образом, исходный вектор остается неизменным. Недостаток очевиден: если вектор большой, копирование его может/будет дорогостоящим. Кроме того, это заканчивает сортировку вектора для каждого запроса, а не сортировку один раз, а затем выполнение как можно большего количества запросов.