Почему я должен суммировать, чтобы найти повторяющиеся числа?

Question

Проблема: вам дана последовательность чисел от 1 до n-1, причем одно из чисел повторяется только один раз.(пример: 1 2 3 3 4 5).как найти повторяющийся номер?

Очень часто так называемый «умный» ответ на этот вопрос состоит в том, чтобы суммировать его и найти разницу от ожидаемой суммы.Но почему бы просто не пройтись по списку и проверить номер перед ним?Оба O (n).Я что-то упустил?

Answer 1

«Умный» ответ - лучшее решение, когда список не отсортирован, поскольку он посещает каждый элемент только один раз и использует O (1) дополнительного пространства. Если список отсортирован по , существует даже решение O (log n): вы можете выполнить двоичный поиск. Посмотрев на центральный элемент, вы можете увидеть, является ли дублирующийся номер до или после этого элемента, и продолжите деление пополам, пока не найдете его.

Пример:

1 2 2 3 4 5 6

Центральным элементом является 3, но он находится на четвертой позиции, поэтому дубликат должен быть перед ним. Следующая проверка - 2 во второй позиции, поэтому мы должны присматривать за второй позицией и т. Д.

Answer 2

Если числа отсортированы, значит, вы ничего не пропустили.

Answer 3

Чтобы узнать загадочное число x, вам нужно только сложить все числа в последовательности:

S = sum(sequence)
S = sum(from 1 to (n - 1)) + x

sum(from A to B) = 1/2 * (A + B) * (B - A + 1)

sum(from 1 to (n - 1)) = 1/2 * (1 + (n - 1)) * ((n - 1) - 1 + 1) = 1/2 * n * (n - 1)

x = S - sum(from 1 to (n - 1))

x = S - 1/2 * n * (n - 1)