Найдите числа, отсутствующие

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

N = 5
1 5 3 2 3

Output: 1 5 4 2 3

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

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

Ответы

Ответ 1

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

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

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

Ответ 2

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

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

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

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

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

Ответ 3

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

Ответ 4

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

Позвольте мне познакомить вас с моим другом Schlemiel the Painter. Открытие более эффективного метода остается для читателя проблемой.

Ответ 5

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

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

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