проверить наличие дубликатов в списке

Question

Как я могу проверить, есть ли в списке дубликаты некоторых элементов со временем тэта (n)?

Это означает, что вы не можете проверить весь список для каждого элемента.

Answer 1

Перебираем элементы и помещаем их в хеш-карту (проверяя наличие коллизий).

Поскольку вставка в хеш-карту - это O (1), вы должны получить O (n) (итерация посписок) + O (1) (вставка и проверка хэш-карты на наличие коллизий, chick обычно является одной из операций большинства реализаций) и O (n) + O (1) -> O (n).