Алгоритмы Java: первый пропущенный положительный результат (LeetCode)

Описание задачи:

По массиву несортированных целых чисел nums вернуть наименьшее отсутствующее положительное целое число.

Условия сложности:

1. Временная сложность: O(n)
2. Пространственная сложность: O(1)

Пример 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Пример 2:

Input: nums = [-1,7,8,9,11,12,-10]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Решение:

Грубая сила

Первое, что приходит на ум, это использовать брутфорс. Идея проста; перебираем все положительные числа от 1, пока не найдем первое пропущенное.

Сложность:

1. Временная сложность: O(n*n)
2. Пространственная сложность: O(1)

public int firstMissingPositive(int[] nums) {
    int positiveNumber = 1;
    while (true) {
        boolean exists = false;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == positiveNumber) {
                exists = true;
                break;
            }
        }
        if (!exists) return positiveNumber;
        positiveNumber++;
    }
}

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

Подход 2: с дополнительным пространством

Мы можем использовать HashMap или логический массив размера N, чтобы запомнить, какие элементы находятся в массиве. А затем простым перебором найти минимальный положительный элемент.

Сложность:

1. Временная сложность: O(n)
2. Пространственная сложность: O(n)

public int firstMissingPositive(int[] nums) {
    Map<Integer, Boolean> map = new HashMap<>();
    for (int n: nums) {
        if (n > 0) {
            map.put(n, true);
        }
    }
    int number = 1;
    while(true) {
        if (map.get(number) == null) {
            return number;
        }
        number++;
    }
}

В первом цикле на строках 3-7 мы запоминаем только положительные числа, так как с ними нам нужно будет работать дальше.

Во втором цикле по строкам 9-13 последовательно проверяем числа начиная с 1. Если число есть на карте, то идем дальше, иначе возвращаем.

:::подсказка Всякий раз, когда мы знаем, как решить проблему с массивом с помощью HashMap, но дополнительное пространство не разрешено, попробуйте использовать сам массив в качестве HashMap.

:::

Подход 3

Чтобы использовать исходный массив в качестве HashMap, нам нужно более внимательно изучить постановку задачи. В худшем случае массив будет содержать все положительные числа от 1 до N (длина массива), и тогда ответ будет N+1.

* Шаг 1. Это означает, что все числа меньше 1 и больше N бесполезны, и мы можем заменить их на N+1. Все числа в массиве теперь положительные и находятся в диапазоне [1..N+1].

* Шаг 2. Мы можем пометить каждую ячейку, которая появляется в массиве, преобразовав индекс для этого числа в отрицательный

* Шаг 3. Найдите первый положительный индекс, который является нашим ответом.

Сложность:

1. Временная сложность: O(n)
2. Пространственная сложность: O(1)

public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    int fakeNumber = n + 1;

    // Step 1.
    for (int i = 0; i < n; i++) {
        if (nums[i] <= 0 || nums[i] > n) {
            nums[i] = fakeNumber;
        }
    }

    // Step 2.
    for (int i = 0; i < n; i++) {
        int num = Math.abs(nums[i]); // point 1
        if (num == fakeNumber) { // point 2
            continue;
        }
        num--; // point 3
        if (nums[num] > 0) {
            nums[num] *= -1;
        }
    }

    // Step 3.
    for (int i = 0; i < n; i++) {
        if (nums[i] >= 0) {
            return i + 1;
        }
    }

    // otherwise return n+1
    return n + 1;
}

Я хотел бы обратить ваше внимание на несколько основных моментов:

1. Поскольку мы помечаем ячейки отрицанием, мы должны игнорировать знак при извлечении.

2. На шаге 1 мы изменили все числа, чтобы игнорировать fakeNumber, поэтому не забудьте их игнорировать.

3. Не забудьте уменьшить значение на 1; так как в java индексирование начинается с нуля (поэтому число 1 будет в позиции 0).

Приведенный выше алгоритм дает нам следующий результат.

Я надеюсь, что эта статья помогла вам понять, как решить проблему такого типа. Буду рад вашим отзывам.

До скорой встречи! ✌