«1. Обзор

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

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

2. Объяснение проблемы

Во-первых, давайте объясним, какова цель алгоритма. Мы хотим найти наименьшее пропущенное положительное целое число в массиве положительных целых чисел. То есть в массиве из x элементов найдите наименьший элемент между 0 и x – 1, которого нет в массиве. Если массив содержит их все, то решением является x, размер массива.

Например, рассмотрим следующий массив: [0, 1, 3, 5, 6]. В нем 5 элементов. Это означает, что мы ищем наименьшее целое число от 0 до 4, которого нет в этом массиве. В данном конкретном случае это 2.

Теперь давайте представим другой массив: [0, 1, 2, 3]. Поскольку он состоит из 4 элементов, мы ищем целое число от 0 до 3. Ни одно из них не пропущено, поэтому наименьшее целое число, отсутствующее в массиве, равно 4.

3. Отсортированный массив

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

Рассмотрим следующий отсортированный массив: [0, 1, 3, 4, 6, 7]. Теперь давайте посмотрим, какое значение соответствует какому индексу: 

Index: 0 1 2 3 4 5
Value: 0 1 3 4 6 7

Как мы видим, индекс значения не содержит целого числа 2, поэтому 2 — это наименьшее отсутствующее целое число в массиве.

Как насчет реализации этого алгоритма на Java? Давайте сначала создадим класс SmallestMissingPositiveInteger с методом searchInSortedArray(): 

public class SmallestMissingPositiveInteger {
    public static int searchInSortedArray(int[] input) {
        // ...
    }
}

Теперь мы можем выполнить итерацию по массиву и найти первый индекс, который не содержит себя как значение, и вернуть его как результат: ~ ~~ 

for (int i = 0; i < input.length; i++) {
    if (i != input[i]) {
        return i;
    }
}

Наконец, если мы завершим цикл, не найдя недостающего элемента, мы должны вернуть следующее целое число, которое является длиной массива, так как мы начинаем с индекса 0: 

return input.length;

Давайте проверим, что все это работает как и ожидалось. Представьте себе массив целых чисел от 0 до 5, в котором пропущено число 3: 

int[] input = new int[] {0, 1, 2, 4, 5};

Тогда, если мы ищем первое пропущенное целое число, должно быть возвращено 3: 

int result = SmallestMissingPositiveInteger.searchInSortedArray(input);

assertThat(result).isEqualTo(3);

Но, если мы ищем пропущенное число в массиве без какого-либо пропущенного целого числа: 

int[] input = new int[] {0, 1, 2, 3, 4, 5};

Мы обнаружим, что первое пропущенное целое число равно 6, то есть длине массива: 

int result = SmallestMissingPositiveInteger.searchInSortedArray(input);

assertThat(result).isEqualTo(input.length);

Далее мы посмотрим, как для обработки несортированных массивов.

4. Несортированный массив

Итак, как насчет поиска наименьшего пропущенного целого числа в несортированном массиве? Есть несколько решений. Первый — сначала просто отсортировать массив, а затем повторно использовать наш предыдущий алгоритм. Другой подход состоит в том, чтобы использовать другой массив, чтобы пометить присутствующие целые числа, а затем пройтись по этому массиву, чтобы найти первое отсутствующее.

4.1. Сначала сортируем массив

Давайте начнем с первого решения и создадим новый метод searchInUnsortedArraySortingFirst().

Итак, мы будем повторно использовать наш алгоритм, но сначала нам нужно отсортировать наш входной массив. Для этого воспользуемся Arrays.sort(): 

Arrays.sort(input);

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

После этого мы можем вызвать наш алгоритм с уже отсортированными входными данными: 

return searchInSortedArray(input);

Вот и все, теперь мы можем проверить, что все работает как положено. Давайте представим следующий массив с несортированными целыми числами и пропущенными числами 1 и 3: 

int[] input = new int[] {4, 2, 0, 5};

Поскольку 1 — наименьшее пропущенное целое число, мы ожидаем, что оно будет результатом вызова нашего метода: 

int result = SmallestMissingPositiveInteger.searchInUnsortedArraySortingFirst(input);

assertThat(result).isEqualTo(1);

Теперь давайте попробуйте на массиве без пропущенных чисел: 

int[] input = new int[] {4, 5, 1, 3, 0, 2};

int result = SmallestMissingPositiveInteger.searchInUnsortedArraySortingFirst(input);

assertThat(result).isEqualTo(input.length);

Вот и все, алгоритм возвращает 6, то есть длину массива.

4.2. Использование логического массива

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

«Во-первых, давайте создадим третий метод, searchInUnsortedArrayBooleanArray().

После этого давайте создадим логический массив flags и для каждого целого числа во входном массиве, которое соответствует индексу логического массива, мы установим соответствующее значение в true: 

boolean[] flags = new boolean[input.length];
for (int number : input) {
    if (number < flags.length) {
        flags[number] = true;
    }
}

Теперь наш массив flags истинно для каждого целого числа, присутствующего во входном массиве, и ложно в противном случае. Затем мы можем перебрать массив флагов и вернуть первый индекс, содержащий false. Если нет, мы возвращаем длину массива: 

for (int i = 0; i < flags.length; i++) {
    if (!flags[i]) {
        return i;
    }
}

return flags.length;

Снова попробуем этот алгоритм на наших примерах. Сначала мы повторно используем массив, в котором отсутствуют 1 и 3: 

int[] input = new int[] {4, 2, 0, 5};

Затем, при поиске наименьшего пропущенного целого числа с помощью нашего нового алгоритма, ответ по-прежнему равен 1: 

int result = SmallestMissingPositiveInteger.searchInUnsortedArrayBooleanArray(input);

assertThat(result).isEqualTo(1);

И для всего массива ответ тоже не меняется и по-прежнему равен 6: 

int[] input = new int[] {4, 5, 1, 3, 0, 2};

int result = SmallestMissingPositiveInteger.searchInUnsortedArrayBooleanArray(input);

assertThat(result).isEqualTo(input.length);

5. Сложности

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

5.1. Сортированный массив

Начнем с первого алгоритма, для которого входные данные уже отсортированы. В этом случае наихудшим сценарием является не поиск пропущенного целого числа и, следовательно, обход всего массива. Это означает, что у нас есть линейная сложность, которая обозначается как O(n), учитывая, что n — это длина нашего ввода.

5.2. Несортированный массив с алгоритмом сортировки

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

Начиная с Java 11, метод Arrays.sort() использует алгоритм быстрой сортировки с двумя опорными точками для сортировки массивов. Сложность этого алгоритма сортировки, как правило, O(n log(n)), хотя он может ухудшиться до O(n²). Это означает, что сложность нашего алгоритма в целом будет O(n log(n)) и может также ухудшиться до квадратичной сложности O(n²).

Это для временной сложности, но давайте не будем забывать о пространстве. Хотя алгоритм поиска не занимает дополнительного места, его занимает алгоритм сортировки. Алгоритм быстрой сортировки занимает до O(log(n)) пространства для выполнения. Это то, что мы можем захотеть учитывать при выборе алгоритма для больших массивов.

5.3. Несортированный массив с логическим массивом

Наконец, давайте посмотрим, как работает наш третий и последний алгоритм. Для этого мы не сортируем входной массив, что означает, что мы не страдаем от сложности сортировки. На самом деле мы просматриваем только два массива одинакового размера. Это означает, что наша временная сложность должна быть O(2n), что упрощается до O(n). Это лучше, чем предыдущий алгоритм.

Но когда дело доходит до пространственной сложности, мы создаем второй массив того же размера, что и входные данные. Это означает, что у нас O(n) пространственная сложность, что хуже, чем у предыдущего алгоритма.

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

6. Заключение

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

Как обычно, полные примеры кода, показанные в этой статье, доступны на GitHub.