Пройдите по слайсу и храните уже встреченные значения в map[int]struct{}. Новое значение добавляйте и в map, и в результирующий слайс. Это сохраняет порядок первых появлений и не меняет исходник. Ожидаемое время O(n), дополнительная память O(u), где u — число разных значений.
Как удалить дубликаты из слайса в Go без внешних библиотек?
Дедупликация []int через map с сохранением порядка первых появлений: код, сложность и альтернативы при ограниченной памяти.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Предположим, дан []int, нужно сохранить порядок первого появления каждого числа и не изменять исходные данные. Для отметки встреченных значений достаточно стандартной map:
func unique(values []int) []int {
seen := make(map[int]struct{})
result := make([]int, 0)
for _, value := range values {
if _, exists := seen[value]; exists {
continue
}
seen[value] = struct{}{}
result = append(result, value)
}
return result
}
Для [3, 1, 3, 2, 1] результат — [3, 1, 2]. Порядок берётся из исходного слайса, а не из обхода map. Возвращать ключи map отдельным циклом нельзя, если порядок является частью требования: Go не гарантирует порядок итерации по map.
struct{} обозначает только факт присутствия, без полезного значения. Проверка exists работает и для нуля, отрицательных чисел и любых других int. Пустой или nil-вход вернёт пустой ненулевой слайс; если контракт требует именно nil, это оговаривают отдельно.
При обычных предположениях о хеш-таблице время линейно в среднем, а map и результат требуют память пропорционально числу уникальных значений. Это не алгоритм без дополнительной памяти. Если память важнее скорости, можно проверять каждое значение по уже накопленному результату за O(n²). Если порядок не важен, другой вариант — сортировка и удаление соседних повторов, с учётом изменения исходника.
Для обобщённого решения тип элементов должен допускать нужное сравнение; срез нельзя напрямую сделать ключом map. Для NaN в числах с плавающей точкой нужна отдельная политика равенства. Тип map в спецификации Go.