Найти пропавшие цифры

Question

Если у нас есть массив всех чисел до N (N <10), каков наилучший способ найти все пропущенные числа. Пример: </p>

N = 5
1 5 3 2 3

Output: 1 5 4 2 3 

В прошлом число 4 было недостающим, и было 2 3 с, поэтому мы заменили первое на 4, и теперь массив завершен - все числа до 5 есть.

Есть ли простой алгоритм, который может это сделать?

Answer 1

Так как N действительно мало, вы можете использовать F [i] = k, если число i появляется k раз.

int F[10]; // make sure to initialize it to 0
for ( int i = 0; i < N; ++i )
  ++F[ numbers[i] ];

Теперь, чтобы заменить дубликаты, обойдите массив чисел, и если текущее число появляется более одного раза, уменьшите его счетчик и замените его на число, которое появляется в 0 раз, и увеличьте счет этого числа. Вы можете оставить это O (N), если сохраните список чисел, которые вообще не появляются. Я дам вам понять, что именно нужно сделать, так как это звучит как домашнее задание.

Answer 2

Допустим, все числа в диапазоне 1 ≤ x ≤ N.

Сохраните 2 массива размером N. output, used (как ассоциативный массив). Инициализируйте их все до 0.

Сканирование с вправо , введите значения до output, если оно не used.

Проверьте наличие неиспользуемых значений и поместите их в пустые (нулевые) слоты output по порядку.

O (N) сложность времени, O (N) сложность пространства.

Answer 3

Вот ссылка, которую я прочитал только сегодня, которая может быть полезна. http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html

Answer 4

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

Мой совет на данный момент таков: если бы вы делали это вручную, как бы вы это сделали? Вы могли бы выписать дополнительный список чисел за какое-то время, вы бы прочитали список (сколько раз?)? и т.д.

Для простых задач иногда хорошо работает моделирование вашего алгоритма после интуитивного ручного подхода.

Answer 5

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

Позвольте представить вам моего друга Шлемьель Художник . Поиск более эффективного метода остается проблемой для читателя.

Answer 6

Вы можете использовать заданную структуру данных - одну для всех чисел до N, одну для чисел, которые вы действительно видели, и использовать установленную разницу.