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

Question

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

Этот вопрос был задан ранее но я не могу найти его для C ++.

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

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

Например, учитывая: vector foo{13,8,3,6,10,1,7,0};

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

РЕДАКТИРОВАТЬ:

Пока что все решения требуют сортировки. Это на самом деле может потребоваться, но временная сортировка vector должно быть создано, чтобы приспособить это, как foo должен остаться без изменений.

3

algorithm c++counting missing-data vector

Решение

Другие решения

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

4

Сначала нужно отсортировать вектор. использование станд :: сортировать для этого.
станд :: 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;

3

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

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

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

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

1

Источник

Accepted Answer

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

Если вы хотите сделать это с чем-то вроде сложности 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 функция. Таким образом, исходный вектор остается неизменным. Недостаток очевиден: если вектор большой, его копирование может / будет дорогостоящим. Кроме того, это заканчивается сортировкой вектора для каждого запроса вместо одной, а затем выполнением столько запросов, сколько необходимо для него.

6