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