Постановка задачи :
Вам дан массив целых чисел длины N, найдите первое пропущенное положительное число за линейное время и постоянное пространство. Другими словами, найдите наименьшее положительное целое число, не существующее в массиве. Массив также может содержать отрицательные числа.
Пример ввода:
N = 5 Arr = {3, 2, -6, 1, 0}
Пример вывода:
4
Объяснение для тестового случая:
Первое положительное число равно 1, и оно присутствует в массиве точно так же, как 2 и 3 также присутствуют в массиве. 4 отсутствует в массиве. Таким образом, минимальное положительное целое число, которое отсутствует, равно 4.
Подход :
Сегрегация
- Вызовите функцию, которая разделит положительное целое число на отрицательное целое, т. е. переместит все неположительные элементы в правую сторону и вернет индекс, с которого начинаются неположительные целые числа.
- Теперь мы можем игнорировать неположительные элементы и рассматривать только ту часть массива, которая содержит все положительные элементы. Мы проходим по массиву, содержащему все положительные числа. Чтобы отметить наличие элемента arr[i], мы меняем знак значения по индексу arr[i] на отрицательный, т.е. помечаем наличие элемента 1, делая элемент массива с индексом 1 отрицательным, учитывая, что индекс лежит в этом сегменте положительных элементов.
- Чтобы найти наименьший положительный недостающий элемент, мы снова проходим массив положительных элементов и печатаем первый индекс, который имеет положительное значение. В случае, если все элементы отрицательные, наш индекс равен размеру — 1. Мы вычитаем 1 из индекса, и это будет ответ.
Временная сложность = O(N)
Пространственная сложность = O(1)
Код :
Спасибо за чтение
Placewit воспитывает лучших инженеров, предоставляя интерактивные занятия в классе и помогая им развивать свои навыки и попадать в замечательные компании.
Узнайте больше на Placewit. Следите за нами в Instagram и Facebook для ежедневного обучения.