Повторяющиеся элементы (Find Duplicates)

Условие

Повторяющиеся элементы (Find Duplicates)

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

Входные данные: []string — слайс строк

Выходные данные: []string — строки, встречающиеся более одного раза, в порядке первого появления

Ограничения:

• 0 <= len(input) <= 10^4
• Каждая строка состоит из латинских букв, длина строки 1..50

Пример: Вход: ["a", "bb", "bb", "aa", "a", "a"] Выход: ["a", "bb"]

def find_duplicates(items): # TODO: напишите решение здесь return []

Ответ

Сначала посчитайте частоты, затем пройдите исходный порядок и добавьте каждый повторяющийся элемент один раз. Так сохраняется порядок первого, а не второго появления.

В условии упомянут Go-слайс, но шаблон функции дан на Python; решение следует шаблону.

from collections import Counter

def find_duplicates(items):
    counts = Counter(items)
    result = []
    added = set()
    for item in items:
        if counts[item] > 1 and item not in added:
            result.append(item)
            added.add(item)
    return result

Для примера результат ['a', 'bb']. В среднем O(n) времени и O(n) памяти при ограниченной длине строк; пустой вход возвращает пустой список.