Нахождение отсутствующего и повторяющегося целого числа из несортированного списка последовательных целых чисел

Question

Этот вопрос очень похож на Как найти дублирующий элемент в массиве перемешанных последовательных целых чисел? , но имеет некоторые дополнительные требования.

У вас есть список последовательных целых чисел в произвольном порядке. Не гарантируется диапазон этих целых чисел или количество элементов в списке.

В этом списке отсутствует одно целое число и содержится копия другого целого числа.

Примером такого списка является {16, 12, 13, 17, 14, 13}; в этом случае отсутствующее целое число равно 15, а дублированное - 13 *. 1009 *

Каков наиболее эффективный по времени способ найти оба этих числа, принимая во внимание как маленькие, так и большие наборы данных? Есть ли какое-либо решение с лучшей временной сложностью, чем O (n log n), которое не душит небольшие наборы данных?

Answer 1

На самом деле вы можете применить идею из указанной темы. Но так как у вас есть два изменения, вы должны измерить две вещи.

Например, измерьте сумму значений и сумму квадратов и сравните их с ожидаемыми. Если номер A дублируется, а номер B отсутствует, у вас будет:

• сумма - ожидаемая сумма = A-B
• sum_of_squares - ожидаемая_сумма_квадрат = A ^ 2-B ^ 2

Имея (A-B) и (A ^ 2-B ^ 2) вы можете получить (A + B) = (A ^ 2-B ^ 2) / (A-B).

Имея (A + B) и (A-B) вы можете получить A = (A + B) / 2 + (A-B) / 2 и B = (A + B) / 2- (A-B) / 2