Как найти K пропущенных чисел в целочисленном массиве с дубликатами в Java?

Прошло много времени с тех пор, как я обсуждал какие-либо вопросы о кодировании или алгоритме , поэтому я решил вернуться к одной из самых популярных проблем кодирования на основе массива — найти пропущенные числа в данном массиве . Возможно, вы уже слышали или видели эту проблему на своем собеседовании по программированию, но существует множество различных версий повышения уровня сложности, которые интервьюер обычно использует, чтобы запутать кандидата и дополнительно проверить его способность адаптироваться к частым изменениям. В прошлом я демонстрировал, как найти отсутствующее число в отсортированном массиве, а также в несортированном целочисленном массиве в Java, используя BitSet (см. Здесь ), но только с одним отсутствующим числом и без дубликатов.

Это несколько облегчает проблему, но что вы будете делать, если интервьюер скажет вам, что массив содержит дубликаты и более одного числа отсутствуют? Ну, это то, что мы обсудим в этой статье, но перед этим давайте правильно сформулируем задачу.

1. Постановка проблемы:

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

Например, если данный массив
{1, 1, 2, 3, 5, 5, 7, 9, 9, 9}, то имеет длину
10 и содержит числа от 1 до 9. В этом случае пропущенными числами являются 4, 6 и 8.

2. Решение:

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

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

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

Мы можем использовать массив в качестве регистра и его индекс в качестве имен чисел. Мы перебираем данный массив и помечаем галочкой все имеющиеся числа, сохраняя один из их соответствующих индексов. Например, если первое число в данном массиве равно 5 (поскольку массив не отсортирован), то мы сохраняем 1 в индексе 5, например, register[5] = 1

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

Это решение также защищено от дубликатов, потому что если число приходит один или два раза, мы просто сохраняем 1 в соответствующем индексе.

3. Код:

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

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

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

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

Вот краткое описание алгоритма и кода на слайде для лучшего понимания:

4. Анализ

Теперь настало время проанализировать наше решение, чтобы определить сложность ЦП и памяти с помощью обозначения Big O. Если вы посмотрите на код, то обнаружите, что мы создаем другой массив с тем же размером, что означает, что он имеет сложность памяти или пространства O (n) .

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

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

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

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

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