В массиве любого размера с целыми числами от 1 до 500,000 одно число повторяется дважды, все остальные числа уникальны. Предложите наиболее быстрый алгоритм поиска повторяющегося числа. Можете выполнить на C, C

1

Ответы и объяснения

  • IUV
  • Ведущий Модератор
2013-05-25T03:58:23+04:00

Это Проверенный ответ

×
Проверенные ответы содержат надёжную, заслуживающую доверия информацию, оценённую командой экспертов. На "Знаниях" вы найдёте миллионы ответов, правильность которых подтвердили активные участники сообщества, но Проверенные ответы - это лучшие из лучших.

1 создать вспомогательный массив с индексами от 0 до 500 например массив А (i) - число повторений числа i
все члены массива обнулить, в цикле по i A(i)= 0
2 пусть С(j) - исходный массив целых чисел
3 в цикле по j сделать операцию A(С(j))+=1 (или A(С(j))++) и проверить, не равно ли A(С(j)) двум

например повторяется число 30
сначала А(30) = 0
потом при первом упоминании А(30) = 1
при следующем А(30)=2

С( j ) - при котором выполнилось A(С(j)) = 2 и есть искомое число