Недостающее число Интервью Вопрос Редукс

Общая проблема интервью с определением недостающего значения в диапазоне от 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, не разумно будет использовать более компьютерный научный/алгоритмический подход, предполагая, что подход соответствует теоретико-множественной сложности решения...

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

Ответ 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) простым переводом.

ИЗМЕНИТЬ

Изменен вид 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), но я не уверен в этом.

Ответ 2

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

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

Ответ 3

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

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

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

Ответ 4

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

Ответ 5

Если диапазон дается вам хорошо, в этом случае диапазон [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}

Ответ 6

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

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

То, что осталось в вашем наборе, - это недостающие номера.