Daily bit(e) C++. Наименьшее пропущенное положительное целое число
Daily bit(e) C++ #9, распространенный вопрос на собеседованиях: наименьшее пропущенное положительное целое число.
Сегодня мы рассмотрим распространенную задачу на собеседованиях – «наименьшее пропущенное целое число».
Задан список целых чисел, определите наименьшее пропущенное положительное целое число. Важно отметить, что ваше решение должно выполняться за время O(n), и хотя вам разрешено изменять входные данные, вы можете использовать только константную дополнительную память.
Например, для входных данных {3, -1, 0, 4, 1} наименьшее пропущенное положительное число равно 2; для ввода {1, 2, 3} наименьшее пропущенное положительное число равно 4.
Прежде чем прочесть решение, попробуйте решить задачу самостоятельно. Вот ссылка на Compiler Explorer с несколькими тестовыми случаями: https://compiler-explorer.com/z/G7r4rebhd.
Решение
Тривиальным решением будет сортировка наших входных данных. Однако это даст временную сложность O(n*logn).
Хотя это не совсем неправильное направление для исследования.
Важно отметить, что недостающее число должно находиться в диапазоне [1, N+1], и оно будет N+1 только в том случае, если входные данные содержат все числа в диапазоне [1, N]. Нам также не важны дубликаты.
Эти две точки позволяют нам сформулировать более простую квази-сортировку, потому что мы знаем индекс назначения каждого из чисел в диапазоне [1, N]; это диапазон индексов [0, N-1].
Мы можем за один проход перебрать наши входные данные, помещая каждое число в нужное место.
Затем, чтобы определить, какое число отсутствует, мы снова перебираем входные данные и возвращаем отсутствующее число или N+1, если заканчиваем перебор входных данных, не находя ни одного.
int lowest_missing(std::vector<int> data)
{
// "сортировка" O(n)
for (auto idx : std::views::iota(0z, std::ssize(data)))
{
while (data[idx] > 0 && // если положительное число
data[idx] - 1 < std::ssize(data) && // и подходит
data[idx] != data[data[idx] - 1] && // это не пустая операция
data[idx] - 1 != idx) // и не на правильном месте
std::swap(data[idx], data[data[idx] - 1]); // перемещаем на правильное место
}
// O(n), потому что каждое число меняется местами не более двух раз
// - сначала подтягивается к текущему индексу
// - затем ставится на конечное место
// поиск O(n)
for (auto idx : std::views::iota(0z, std::ssize(data)))
{
if (data[idx] - 1 != idx)
return idx + 1;
}
return std::ssize(data)+1;
}Открыть решение на Compiler Explorer.