Сложность: hard
Дан неотсортированный массив целых чисел nums. Верните наименьшее положительное целое число, которого нет в массиве nums.
Необходимо реализовать алгоритм, который работает за время O(n) и использует O(1) дополнительной памяти.
Пример:
Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.
👨💻 Алгоритм:
1⃣Инициализировать переменную n длиной массива nums. Создать массив seen размером n + 1. Отметить элементы в массиве nums как просмотренные в массиве seen.
Для каждого числа num в массиве nums, если num больше 0 и меньше или равно n, установить seen[num] в значение true.
2⃣Найти наименьшее недостающее положительное число:
Проитерировать от 1 до n, и если seen[i] не равно true, вернуть i как наименьшее недостающее положительное число.
3⃣Если массив seen содержит все элементы от 1 до n, вернуть n + 1 как наименьшее недостающее положительное число.
😎 Решение:
func firstMissingPositive(_ nums: [Int]) -> Int {
let n = nums.count
var seen = Array(repeating: false, count: n + 1)
for num in nums {
if num > 0 && num <= n {
seen[num] = true
}
}
for i in 1...n {
if !seen[i] {
return i
}
}
return n + 1
}Ставь 👍 и забирай 📚 Базу знаний