Кандидат: Можно отсортировать массив. Повторяющиеся элементы будут рядом, мы легко можем их найти.
Интервьюер: Тогда временная сложность вырастет до O(NLogN). Что ещё можно сделать?
А если массив A = 1,2,3,...,n,n?
И, сходу, быстрая сортировка — уже n^2.
Ладно, пусть отсортировали за n*ln(n)
Но теперь ещё надо пройти по всему массиву — итог n^2*ln(n).
from collections import Counter
print(list(Counter(A))[0])
А если массив A = 1,2,3,...,n,n?
И, сходу, быстрая сортировка — уже n^2.
Ладно, пусть отсортировали за n*ln(n)
Но теперь ещё надо пройти по всему массиву — итог n^2*ln(n).
from collections import Counter
print(list(Counter(A))[0])
За нас уже подумали; и код лаконичный.