Задача с собеседования: First Missing Positive

Задача.

Дан неотсортированный массив целых чисел. Нужно найти первое пропущенное положительное число.

Например,
для [1,2,0] ответ 3.
для [3,4,-1,1] ответ 2.
для [7,8,9,11,12] ответ 1.

Решение должно работать за O(n) и с O(1) дополнительной памяти.

Ссылка на leetcode: https://leetcode.com/problems/first-missing-positive/description/

Решение

Сразу в голове могут возникнуть такие решения:

1) Используя хэш-таблицу. Если длинна массива n, то первое положительное пропущенное число будет от 1 до n + 1. n + 1 может быть в том случае, если у нас в массиве есть все числа от 1 до n. Например, массив вида 1, 2, 3, 4, 5, .., n. Тогда первое пропущенное число будет n + 1. Больше чем n + 1 оно быть не может. Поэтому мы может объявить хэш-таблицу, с ключами 1, 2, 3, ..., n + 1. А в качестве значения будет true или false, в зависимости от того, есть ли такое число в массиве или нет. Мы можем пройти по массиву и если текущий элемент массива от 1 до n + 1, то просто помечать его в таблице значением true. После этого пройтись циклом по хэш-таблице и найти наименьшее пропущенное число.
Алгоритмическая сложность: O(n), сложность по памяти O(n).
Код:

class Solution {
    public int firstMissingPositive(int[] nums) {
        Map<Integer, Boolean> map = new HashMap<>();
        for (int i = 1; i <= nums.length + 1; i++) {
            map.put(i, false);
        }
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], true);
            }
        }
        int result = Integer.MAX_VALUE;
        for (int key : map.keySet()) {
            if (!map.get(key)) {
                result = Math.min(result, key);
            }
        }
        return result;
    }
}

2) Можно немного сократить код, если у нас в хэш-таблице ключи упорядоченны и нам не надо искать минимальный ключ со значением false.
Для этого можно вместо HashMap использовать LinkedHashMap.

class Solution {
    public int firstMissingPositive(int[] nums) {
        Map<Integer, Boolean> map = new LinkedHashMap<>();
        for (int i = 1; i <= nums.length + 1; i++) {
            map.put(i, false);
        }
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], true);
            }
        }
        for (int key : map.keySet()) {
            if (!map.get(key)) {
                return key;
            }
        }
        return -1;
    }
}

Алгоритмическая сложность: O(n), сложность по памяти O(n).

3) Можно вместо HashMap использовать вспомогательный массив длинны n + 1. Аналогом ключа в Hash-таблице будет индекс массива. А в качестве значения можно также использовать true или false.
код:

class Solution {
    public int firstMissingPositive(int[] nums) {
        boolean map[] = new boolean[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 1 && nums[i] <= nums.length + 1) {
                map[nums[i] - 1] = true;
            }
        }
        for (int i = 0; i < nums.length + 1; i++) {
            if (!map[i]) {
                return i + 1;
            }
        }
        return -1;
    }
}

Алгоритмическая сложность: O(n), сложность по памяти O(n).

Но все эти решения работают по памяти за O(n). А нам надо без дополнительной памяти.

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

Cycle Sorting

Для этого можно применить такой подход, как Cycle Sorting. Этот подход иногда применим для задач с целочисленными массивами.

Давайте сначала рассмотрим классическую задачу для Cycle Sorting.

Пусть у нас есть целочисленный массив длинны n, в котором есть только числа от 1 до n, но в произвольном порядке. Нам надо отсортировать этот массив за O(n) с O(1) дополнительной памяти.
Например, для массива
[2, 6, 4, 3, 1, 5]
Нам надо получить [1, 2, 3, 4 , 5, 6].

Наша цель поместить каждое число на правильное место в отсортированным массиве.

Какое место в массиве правильное для произвольного числа nums[i]? Правильный индекс для nums[i] это correct_index = nums[i] - 1;
Действительно, давайте посмотрим на i = 1. nums[1] = 6. correct_index = nums[1] - 1 = 6 - 1 = 5. Т.е. правильный индекс для 6 это индекс 5 (в хвосте массива).

Мы можем пройтись по массиву, проверить, находится ли число на своем месте. Если да, то перейдем к следующему элементу массива. Если не на своем, то поместим его на свое место, а то число которое было на его правильном месте поместим на текущий индекс (поменяем местами). Если новое, число, которое мы получили после перестановки, также на своем месте, то идем дальше. Если нет, то поместим его на правильное место путем перестановки и повторим все еще раз и т.д.

Давайте сделаем это шаг за шагом для массива [2, 6, 4, 3, 1, 5]

Вначале i = 0.

nums[0] = 2. Для него правильный индекс correct_index = nums[0] - 1 = 2 - 1 = 1. А оно на позиции 0. Т.е. не на своем месте. Поместим двойку на свое месте, а число, которое было по индексу 1, поместим на место двойки.

Теперь в ячейке i = 0 у нас 6. correct_index = nums[0] - 1 = 6 - 1 = 5. Т.е. 6 не на своем месте - произведем перестановку.

Теперь в ячейке i = 0 у нас 5. correct_index = nums[0] - 1 = 5 - 1 = 4. Т.е. 5 не на своем месте - произведем перестановку.

Теперь в ячейке i = 0 у нас 1. correct_index = nums[0] - 1 = 1 - 1 = 0. Т.е. 1 на своем месте. Перестановка не нужна. Перейдем к следующей ячейке массива.

В текущей ячейке i = 1 лежит значение 2. correct_index = nums[1] - 1 = 2 - 1 = 1. Т.е. двойка на своем месте. Идем дальше.

В i = 2 у нас nums[2] = 4. correct_index = 3. Делаем перестановку.

Теперь у нас в nums[2] = 3. correct_index = 3 - 1 = 2. Т.е. 3 у нас на своем месте. Идем дальше.

Дальше у нас все элементы на своем месте. Никаких перестановок не потребуется. Когда дойдем до конца массива - алгоритм завершен.

Код алгоритма:

void sort(int nums[]) {
    int i = 0;
    while (i < nums.length) {
        int correct_index = nums[i] - 1;
        if (i != correct_index) {
            swap(nums, i, correct_index);
        } else {
            i++;
        }
    }
}

void swap (int nums[], int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

Оптимальное решение исходной задачи

Переиспользуем Cycle Sort для решения данной задачи. По сути, нам надо отсортировать массив используя Cycle Sort и найти первый элемент, который после сортировки не на своем месте в массиве и вернуть его индекс + 1 в качестве результата.
Например, для массива [3,4,-1,1]
после сортировки получим: [1, -1, 3, 4]. Первый элемент, который не на своем месте это -1 по индексу 1. Тогда ответ будет 2. Но для этого нам немного нужно расширить наш код сортировки.
Условие:

if (i != correct_index) 

нужно дополнить условиями, что число от 1 до n + 1. Все остальные мы будем игнорить, т.к. для них нет корректного места в конечном отсортированном массиве. Оно будет за пределами массива:

if (i != correct_index && nums[i] > 0 && nums[i] <= nums.length)

Более того, в условии не сказано, что у нас все числа уникальны. У нас могут быть дубликаты. Поэтому нам надо добавить условие:

nums[i] != nums[correct_index]

Чтобы предотвратить бесконечный цикл. Иначе мы будем бесконечно менять местами одно и тоже число.
Тогда финальное условие:

if (i != correct_index  && nums[i] > 0 
    && nums[i] <= nums.length 
    && nums[i] != nums[correct_index]) {

Для массива [7,8,9,11,12], у нас все элементы будут проигнорированны, т.к. для всех элементов nums[i] > nums.length. Поэтому сортировка оставит массив без изменений. И после мы сразу определим, что 7 не на своем месте. Она на индексе 0, поэтому ответ индекс + 1 = 0 + 1 = 1.

Финальный код:

class Solution {
    public int firstMissingPositive(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            int correct_index = nums[i] - 1;
            if (i != correct_index  && nums[i] > 0 
                && nums[i] <= nums.length 
                && nums[i] != nums[correct_index]) {
                swap(nums, i, correct_index);
            } else {
                i++;
            }
        }
        for (i = 0; i < nums.length; i++) {
            int correct_index = nums[i] - 1;
            if (i != correct_index) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }

    void swap(int nums[], int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}