Задача с собеседования: Поиск удаленного элемента за O(N)

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

Спойлер: это не так. Иногда для решения задачи достаточно всего лишь базового знания языка и немного фантазии.

Давайте рассмотрим одну из таких задач и разберем ее решение на примере языка Python. Уверены, что на любой другой язык Вы перенесете это решение без каких-либо проблем :)

Формулировка задачи

Итак, задача.

Дана упорядоченная последовательность чисел от 1 до N. Одно из чисел удалили. Оставшиеся числа перемешали в случайном порядке. Найдите удаленное число.

Кстати говоря, точно такая же задача часто встречается под соусом «Найти дубль в числовой последовательности». Ход рассуждений точно такой же :)

Решение в лоб

Казалось бы - решение задачи очевидно. Мы же можем снова отсортировать перемешанную последовательность. После этого сравниваем изначальную последовательность и получившуюся до первого несовпадения. Как только встретили расхождение - вот он, ответ! Ларчик-то просто открывался.

Однако, не все так просто. Конечно, задачу Вы решили, но крайне не оптимальным способом. Посудите сами - сложность сортировки перемешанной последовательности O(NlogN), в случае какой-нибудь быстрой сортировки или сортировки слиянием. Помимо этого, мы еще выполняем поиск расхождения в отсортированных массивах. Поиск в отсортированном массиве имеет сложность O(N), т.е. в худшем случае, если удалили самый большой элемент, нам придется перебрать весь массив.

Итого сложность алгоритма: O(NlogN) + O(N) = O(NlogN).

Неплохо, но можно и лучше. Как минимум, за O(N)!

Правильное решение

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

А зачем нам тогда информация о том, что в начале список был отсортирован, а потом его перемешали? Все просто - чтобы сбить с толку кандидата и проверить его внимательность :)Итак, вот простой алгоритм, который нужно реализовать:

1. Найти сумму начальной последовательности
2. Найти сумму перемешанной последовательности
3. Вычесть из первого второе - это и есть результат

На языке Python решение займет две строки (функция findDel):

import random

arr = list(range(1, 101))
# Генерируем последовательность от 1 до 100

del_index = random.randint(1, 100)
# Случайно выбираем элемент для удаления

randArr = arr[0:del_index-1] + arr[del_index:]
# Удаляем элемент

randArr = random.sample(randArr, 99)
# Перемешиваем
def findDel(arr, randArr):
   n = len(arr)
   # Количество элементов в массиве
   return (arr[0] + arr[n-1])*n/2 - sum(randArr)

res = findDel(arr, randArr)
# Находим удаленное число

По сути, мы делаем три операции.

• Первая - суммирование начальной последовательности. Она идет без пропусков, поэтому мы имеем дело с арифметической прогрессией. Сумма арифметической прогрессии считается по формуле (a_1+a_n)*n/2. Сложность такой операции - O(1), т.к. последовательность упорядочена и при увеличении количества элементов наш расчет никак не усложнится.

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

• Вторая операция - суммирования перемешанного ряда. Это уже не арифметическая прогрессия, т.к. элемент пропущен. Да и последовательность не отсортирована, поэтому мы просто поэлементно складываем все члены, чтобы посчитать сумму. В Python за нас это делает функция sum. Сложность такой операции - O(N), т.к. надо перебрать все элементы.
• Последняя операция - вычесть результат одного из другого. Вычитание двух чисел имеет сложность O(1).

Итого, конечная сложность алгоритма составляет O(1) + O(N) + O(1) = O(N). Не O(1), конечно, но лучше, чем O(NlogN) из первого решения.

Эпилог

Мы с Вами разобрали простейшую задачку, но даже тут есть где разгуляться - можно и более оптимальное решение поискать, и отработать навык расчета сложности алгоритмов.