Постановка задачи :

Вам дан массив целых чисел длины N, найдите первое пропущенное положительное число за линейное время и постоянное пространство. Другими словами, найдите наименьшее положительное целое число, не существующее в массиве. Массив также может содержать отрицательные числа.

Пример ввода:

N = 5
Arr = {3, 2, -6, 1, 0}

Пример вывода:

4

Объяснение для тестового случая:

Первое положительное число равно 1, и оно присутствует в массиве точно так же, как 2 и 3 также присутствуют в массиве. 4 отсутствует в массиве. Таким образом, минимальное положительное целое число, которое отсутствует, равно 4.

Подход :

Сегрегация

  1. Вызовите функцию, которая разделит положительное целое число на отрицательное целое, т. е. переместит все неположительные элементы в правую сторону и вернет индекс, с которого начинаются неположительные целые числа.
  2. Теперь мы можем игнорировать неположительные элементы и рассматривать только ту часть массива, которая содержит все положительные элементы. Мы проходим по массиву, содержащему все положительные числа. Чтобы отметить наличие элемента arr[i], мы меняем знак значения по индексу arr[i] на отрицательный, т.е. помечаем наличие элемента 1, делая элемент массива с индексом 1 отрицательным, учитывая, что индекс лежит в этом сегменте положительных элементов.
  3. Чтобы найти наименьший положительный недостающий элемент, мы снова проходим массив положительных элементов и печатаем первый индекс, который имеет положительное значение. В случае, если все элементы отрицательные, наш индекс равен размеру — 1. Мы вычитаем 1 из индекса, и это будет ответ.

Временная сложность = O(N)
Пространственная сложность = O(1)

Код :

Спасибо за чтение

Placewit воспитывает лучших инженеров, предоставляя интерактивные занятия в классе и помогая им развивать свои навыки и попадать в замечательные компании.

Узнайте больше на Placewit. Следите за нами в Instagram и Facebook для ежедневного обучения.