Задача: 41. First Missing Positive
сложность: 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 как наименьшее недостающее положительное число.

😎 Решение:

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        boolean[] seen = new boolean[n + 1];

        for (int num : nums) {
            if (num > 0 && num <= n) {
                seen[num] = true;
            }
        }

        for (int i = 1; i <= n; i++) {
            if (!seen[i]) {
                return i;
            }
        }

        return n + 1;
    }
}

Ставь 👍 и забирай 📚 Базу знаний