Ежедневный бит (е) 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) "sort"
for (auto idx : std::views::iota(0z, std::ssize(data))) {
while (data[idx] > 0 && // if a positive number
data[idx] - 1 < std::ssize(data) && // and does fit
data[idx] != data[data[idx] - 1] && // this is not noop
data[idx] - 1 != idx) // and not in correct place
std::swap(data[idx], data[data[idx] - 1]); // move in correct place
}
// O(n) because each number is swapped at most twice
// - first pulled to the current index
// - then put into final place
// O(n) search
for (auto idx : std::views::iota(0z, std::ssize(data)))
if (data[idx] - 1 != idx)
return idx + 1;
return std::ssize(data)+1;
}
