Каков самый быстрый способ найти все недостающие номера в несортированном массиве

Я нашел этот ответ: Quickest way to find missing number in an array of numbers, что здорово, когда у вас осталось только одно число.Каков самый быстрый способ найти все недостающие номера в несортированном массиве

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

источник

2016-06-16 Nimrod

«Я задался вопросом, что является лучшим (и самым быстрым) способом поиска всех недостающих чисел, а также для сортировки несортированного массива» - оба одновременно? Или «быстрее всего сортировать» и «быстрее всего за недостающие номера» самостоятельно? – Fildor

моя ошибка - я имел в виду быстрее всего отсутствующих номеров. – Nimrod

Я не думаю, что мы можем сделать это лучше, чем O (n), потому что в аренде один раз нам нужно пройти полный массив, будь то сортировка или поиск недостающих чисел. – pbajpai21

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

Все это работает в O (n).

Пример: Приведен следующий массив 6,1,7,8,3,4,9,1,10,3.

Теперь вычислит, как часто каждое число появляется в массиве, идя один раз через массив и приращение счетчика для каждого встречается номер:

number 1 2 3 4 5 6 7 8 9 10 
count 2 0 2 1 0 1 1 1 1 1

Вы сразу же увидите, что 2 и 5 действительно появлялись 0 раз, и, следовательно, отсутствует.

Подсчеты также могут использоваться для сортировки массива: нам нужно 2 раза 1, два раза 3, один раз 4 и т. Д.

1 1 3 3 4 6 7 8 9 10

источник

2016-06-16 12:29:19 Henry

извините за непонятность (я отредактировал вопрос). сказать, что у меня есть массив с 10 номерами от 1 до 10, и у меня есть, например, числа «2» и «5». вы можете привести пример, пожалуйста? – Nimrod

этот пример замечательный! Я не отчуждаю одну мелочь. вы упомянули, что «все работает на O (n)», но я не понимаю, почему. Во-первых, вы должны над массивом и рассчитать, как часто появляется число, которое уже является O (n), а затем, когда закончите, вы должны перейти и найти «дыры», которые являются еще одним O (n), правильно? Итак, мы пришли к O (n)^2. , и если мы хотим его сортировать, это еще один O (n). Неужели я ошибаюсь? – Nimrod

Почти правильно, но O (n) + O (n) все еще O (n), поэтому в сумме получаем O (n) + O (n) + O (n), который суммируется до O (n). – Henry

Каков самый быстрый способ найти все недостающие номера в несортированном массиве

ответ

Смежные вопросы