Отсутствующие номера Интервью Вопрос Redux

Question

Распространенная проблема опроса при определении пропущенного значения в диапазоне от 1 до N повторялась тысячу раз. Варианты включают 2 пропущенных значения до K пропущенных значений.

Пример задачи: диапазон [1,10] (1 2 4 5 7 8 9 10) = {3,6}

Вот пример различных решений:

Простой вопрос для интервью усложнился: с помощью цифр 1..100 найдите пропущенные числа

Мой вопрос заключается в том, что если рассматривать простой случай, когда одно пропущенное значение имеет сложность O (n), и что сложность больших случаев сходится примерно к чему-то большему, чем O (nlogn):

Не проще ли ответить на вопрос, сказав sort (mergesort) диапазон и выполнить итерацию по нему, наблюдая за отсутствующими элементами?

Это решение должно занимать не более O (nlogn) и способно решить проблему для диапазонов, отличных от 1-N, таких как от 10 до 1000 или от -100 до +100 и т. Д. ...

Есть ли основания полагать, что данные решения в приведенной выше ссылке SO будут лучше, чем решение на основе сортировки для большего числа пропущенных значений?

Примечание. Похоже, что для решения этой проблемы много общих решений, предполагается, что используется только теоретико-числовой подход. Если кто-то задает такой вопрос в интервью S / E, не было бы разумно использовать более информатический / алгоритмический подход, предполагая, что этот подход находится на одном уровне со сложностью теоретико-числового решения ...

Дополнительные ссылки:

• https://mathoverflow.net/questions/25374/duplicate-detection-problem
• Как определить, является ли массив перестановкой в ​​O (n)?

Answer 1

Вы указываете только временную сложность, но также важно учитывать сложность пространства.

Сложность задачи можно указать в терминах N (длина диапазона) и K (количество пропущенных элементов).

В вопросе, который вы связываете, решение использования уравнений - это O (K) в пространстве (или, возможно, немного больше?), Так как вам нужно одно уравнение на неизвестное значение.

Существует также точка сохранения: можете ли вы изменить список известных элементов? В ряде случаев это нежелательно, и в этом случае любое решение, связанное с переупорядочением элементов или их потреблением, должно сначала сделать копию O (N-K) в пространстве.

Я не вижу быстрее линейного решения: вам нужно прочитать все известные элементы (N-K) и вывести все неизвестные элементы (K). Следовательно, вы не можете стать лучше, чем O (N) во времени.

Давайте разберем решения

• Уничтожение, O (N) пространство, O (N log N) время: сортировка по месту
• Сохранение, O (K) пространство?, O (N log N) время: система уравнений
• Сохранение, O (N) пробел, O (N) время: счетная сортировка

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

И что касается времени, то в реальном исполнении, я думаю, «счетная сортировка» превзойдет все остальные решения.

Примечание : для сортировки при подсчете не требуется, чтобы диапазон был [0, X), подойдет любой диапазон, поскольку любой конечный диапазон может быть перенесен в форму [0, X) простым переводом.

EDIT

Изменил сортировку на O (N), для сортировки нужно иметь все элементы.

Когда у меня было время подумать над проблемой, у меня также есть другое решение. Как уже отмечалось, когда N увеличивается (резко), требуемое пространство может взорваться. Однако, если K мало, то мы можем изменить наше представление списка, используя интервалы:

• {4, 5, 3, 1, 7}

можно представить как

• [1,1] U [3,5] U [7,7]

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

Временная сложность проста: O (N log N), в конце концов это в основном вставная сортировка.

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

С другой стороны, мне довольно сложно вычислить среднюю сложность пространства. «Конечное» занимаемое пространство - это O (K) (не более K + 1 интервалов), но во время построения будет гораздо больше пропущенных интервалов, поскольку мы вводим элементы в произвольном порядке.

Худший случай достаточно прост: N / 2 интервалов (думаю, что нечетные против четных чисел). Однако я не могу понять средний случай. Мое инстинктивное чувство говорит мне, что это должно быть лучше, чем O (N), но я не настолько доверчив.

Answer 2

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

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

Answer 3

Если имеется всего N элементов, где каждое число x таково, что 1 <= x <= N </strong>, то мы можем решить это за O (nlogn) сложность времени и O (1) сложность пространства.

1. Сначала отсортируйте массив с помощью быстрой сортировки или слияния.
2. Сканирование через отсортированный массив, и если разница между ранее отсканированным числом a и текущим числом b равна 2 (b - a = 2), то отсутствующее число равно a + 1. Это может быть расширено до условия, где (b - a> 2).

Сложность по времени O (nlogn) + O (n) почти равна O (nlogn), когда N> 100.

Answer 4

Как насчет этого?

1. создать свой собственный набор, содержащий все числа
2. удалить данный набор чисел из вашего набора (не нужно сортировать)

В вашем наборе остались пропущенные числа.

Answer 5

Является ли данное решение теоретически лучше, чем сортировка, зависит от N и K. Хотя ваше решение имеет сложность O(N*log(N)), данное решение равно O(N*K).Я думаю, что данное решение (так же, как и решение для сортировки) способно решить любой диапазон [A, B], просто преобразовав диапазон [A, B] в [1, N].

Answer 6

Если диапазон задан вам намного раньше, в этом случае диапазон [1,10], вы можете выполнить операцию XOR со своим диапазоном и указанными вам числами. Поскольку XOR является коммутативной операцией. Вы останетесь с {3,6}

(1 2 3 4 5 6 7 8 9 10) XOR (1 2 4 5 7 8 9 10) = {3,6}