Дан массив первых n натуральных чисел с одним отсутствующим элементом и одним повторяющимся элементом. Подсчитайте оба числа
Дан массив натуральных чисел first n с одним отсутствующим элементом и одним повторяющимся элементом. выяснить оба числа. Этот вопрос мне задали в одном из интервью.
Например, образец массива
5, 2, 1, 4, 5
where n=5
Ответ для данного массива должен быть:
missing element = 3
duplicate element = 5
Можно ли найти решение без итерации массива.
Мне удалось придумать решение со сложностью O (nlogn) без лишнего места. Существует ли какое-либо решение O (n) (без лишнего места)?
Прочтите обновленное определение проблемы.
Возможности Google: geeksforgeeks.org/find-a-repeating-and-a-missing-number
Ответы 1
Допустим, у вас есть номера 1,...,n. Теперь обозначим их сумму 1 + 2 + ... + n как S. Если мы обозначим недостающее число как j, а двойное как k, мы получим модифицированную сумму S' = S - j + k, так что это одно уравнение для двух переменных. Мы можем повторить ту же процедуру, но на этот раз, суммируя вторые степени, то есть S_2 = 1 + 4 + ... + n^2. Для последовательности с одним пропущенным и одним двузначным числом результатом будет S_2' = S_2 - j*j + k*k. Таким образом, мы получаем два уравнения для двух переменных.
Всего у нас есть:
S' = S - j + k
S_2' = S_2 - j*j + k*k
следовательно
k - j = S' - S =: a
k*k - j*j = S_2' - S_2 =: b
где мы ввели символы a и b для упрощения обозначений.
Теперь k*k - j*j = (k - j)*(k + j), таким образом:
k - j = a
k*k - j*j = a * (k + j) = b
суммирование обоих уравнений дает:
2*k = b/a + a
2*j = b/a - a
Для вашего конкретного примера:
S = 1 + 2 + 3 + 4 + 5 = 15
S_2 = 1 + 4 + 9 + 16 + 25 = 55
Для серии с одним отсутствующим и одним двузначным элементом:
S' = 5 + 2 + 1 + 4 + 5 = 17
S_2' = 25 + 4 + 1 + 16 + 25 = 71
тогда:
a = S' - S = 2
b = S_2' - S_2 = 16
следовательно:
2*k = 8 + 2 = 10
2*j = 8 - 2 = 6
который дает:
k = 5, j = 3
На практике (как отмечает @HermanTheGermanHesse) можно получить замкнутую форму выражения для S, а также для S_2 в терминах полиномов от n (так называемые формулы Фаульхабера), а именно: S = n*(n+1)/2 и S_2 = n*(n+1)*(2*n+1)/6. Поэтому достаточно один раз просмотреть входные данные, накопить S' и S_2' и использовать приведенные выше формулы для k и j ...
Из здесь: S = (n (n + 1)) / 2 S_2 = (n (n + 1) (2n + 1)) / 6 Так что вам не нужно вычислять его шаг за шагом;)
@HermanTheGermanHesse действительно, это должно упростить жизнь! :) Включу в ответ ...
Что вы имеете в виду под «без итерации массива»? Вы имеете в виду, не проверяя их все или не просматривая массив несколько раз?