Алгоритм поиска наименьшего неотрицательного целого числа, которого нет в списке

Question

Учитывая список целых чисел, как мне лучше всего найти целое число, которое не в списке?

Список потенциально может быть очень большим, а целые числа могут быть большими (то есть BigIntegers, а не только 32-битными целыми числами).

Если есть какая-то разница, список «вероятно» отсортирован, то есть 99% времени он будет отсортирован, но я не могу полагаться на то, что сортировка будет всегда.

Редактировать -

Чтобы уточнить, учитывая список {0, 1, 3, 4, 7}, примерами приемлемых решений будут -2, 2, 8 и 10012, но я бы предпочел найти наименьшее, неотрицательное решение ( т.е. 2) если есть алгоритм, который может найти его без необходимости сортировки всего списка.

Answer 1

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

Answer 2

Только что дал интервью, где мне задавали этот вопрос. Ответ на эту проблему можно найти с помощью анализа наихудшего случая. Верхняя граница для наименьшего натурального числа, присутствующего в списке, будет длиной (список). Это потому, что наихудший случай для наименьшего числа, присутствующего в списке, учитывая длину списка, это список 0,1,2,3,4,5 .... длина (список) -1.

Следовательно, для всех списков наименьшее число, отсутствующее в списке, меньше длины списка. Таким образом, начать список t с n = длина (список) +1 нули. В соответствии с каждым номером i в списке (меньше, чем длина списка) отметьте значение 1 для t [i]. Индекс первого нуля в списке - это наименьшее число, отсутствующее в списке. А поскольку нижняя граница в этом списке n-1, для хотя бы одного индекса j

Answer 3

Вам нужен список для сортировки. Это означает либо знание того, что оно отсортировано, либо его сортировку.

• Сортировка списка. Пропустите этот шаг, если известно, что список отсортирован. O (n lg n)
• Удалите все повторяющиеся элементы. Пропустите этот шаг, если элементы уже гарантированно различаются. О (п)
• Пусть B будет позицией 1 в списке с использованием бинарного поиска. O (LG N)
• Если 1 нет в списке, вернуть 1. Обратите внимание, что если все элементы от 1 до n находятся в списке, то элемент в B + n должен быть n + 1. O (1)
• Теперь выполните сортировку двоичного поиска, начиная с min = B, max = конец списка. Назовите положение оси P. Если элемент в точке P больше, чем (P-B + 1), выполните рекурсивный анализ в диапазоне [min, pivot], в противном случае вернитесь в диапазон (pivot, max]. Продолжайте, пока min = pivot = max O (lg n)
• Ваш ответ (элемент в точке-1) +1, если только вы не в конце списка и (P-B + 1) = B, в этом случае это последний элемент + 1. O (1 )

Это очень эффективно, если список уже отсортирован и имеет различные элементы. Вы можете сделать оптимистичные проверки, чтобы сделать это быстрее, когда список содержит только неотрицательные элементы или когда список не содержит значение 1.