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;
}
}
Теперь наш массив флагов имеет значение true для каждого целого числа, присутствующего во входном массиве, и false в противном случае. Затем мы можем перебрать массив флагов и вернуть первый индекс, содержащий 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 .