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

Условие

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

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

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

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

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

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

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

Ответ

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

func FindDuplicates(input []string) []string {
    counts := make(map[string]int, len(input))
    for _, value := range input {
        counts[value]++
    }
    result := make([]string, 0)
    for _, value := range input {
        if counts[value] > 1 {
            result = append(result, value)
            counts[value] = 0
        }
    }
    return result
}

В первом проходе определяем, какие элементы повторяются. Во втором обнуляем счётчик после добавления, поэтому каждое значение попадёт в результат один раз именно в порядке первого появления. Для примера получится ["a", "bb"]. При ограниченной длине строк ожидаемое время O(n), дополнительная память O(k), где k — число различных строк.