Кратко — почему плохо, что исправить, и как сделать лучше.
1) Сложность текущего подхода
- Внутри цикла вызывается `arr.count(x)`, а `count` обходит весь список: для списка длины $n$ один вызов — $O(n)$. Цикл делает до $n$ таких вызовов, получаем временную сложность $O(n^2)$.
- Память: создаются `seen` и `res`, то есть дополнительная память до $O(n)$.
Итого: время $O(n^2)$, память $O(n)$.
2) Ошибки / недостатки
- Небыстро: многократные `arr.count`.
- `seen.add(x)` в коде выполняется для всех элементов; это не ломает результат, но логичнее и чуть эффективнее проверять `x not in seen` перед вызовом `count`.
- Использование `set`/`Counter` требует, чтобы элементы были хешируемы; для списков/словарей (нехешируемых) будет `TypeError`.
- Особые значения: `float('nan')` ведёт себя странно (NaN != NaN), поэтому одинаковые NaN могут не быть посчитаны как одинаковые.
- Порядок: исходный код возвращает дубликаты в порядке их первого появления (потому что добавляет при первой встрече). Это полезно и стоит сохранить при замене.
3) Болеe эффективная и корректная реализация (хешируемые элементы, сохраняет порядок)
- Идея: сначала один проход для подсчёта (Counter/dict), затем проход по `arr`, добавляем элемент в результат при первом обнаружении, если его count > 1.
Пример:
```python
from collections import Counter
def find_duplicates(arr):
counts = Counter(arr) # O(n)
seen = set()
res = []
for x in arr: # O(n)
if counts[x] > 1 and x not in seen:
res.append(x)
seen.add(x)
return res
```
Сложность: время $O(n)$, память $O(n)$.
Если порядок не важен, можно вернуть просто
```python
[x for x, c in counts.items() if c > 1]
```
(в современных Python словари сохраняют порядок вставки, но явный второй проход над `arr` — надежный способ сохранить порядок первого появления).
4) Поддержка нехешируемых элементов (если нужно)
- Для общих элементов (включая списки) словари/множества не работают. Тогда вариант с перебором — корректен, но медленнее:
```python
def find_duplicates_unhashable(arr):
res = []
for i, x in enumerate(arr):
if x in arr[i+1:] and not any(x == y for y in res):
res.append(x)
return res
```
Сложность этого варианта — $O(n^2)$, но он работает с любыми сравнимыми элементами.
5) Пограничные случаи
- Пустой список -> возвращает пустой список.
- Все элементы уникальны -> пустой список.
- Все элементы одинаковые -> результат — один элемент (тот, который впервые встретился).
- Нехешируемые элементы -> `Counter`/`set` вызовет `TypeError`; используйте вариант для нехешируемых либо предварительно преобразуйте элементы.
- NaN: повторяющиеся NaN могут не быть распознаны как равные; если это важно, обработайте `math.isnan` отдельно.
Резюме: исходный код имеет временную сложность $O(n^2)$ из‑за `arr.count` в цикле. Лучший подход — один проход для подсчёта и второй для сбора дубликатов (временная сложность $O(n)$, память $O(n)$), либо специальная обработка для нехешируемых и NaN.