Исключить всех innocents из suspects (разность множеств)
Даны два слайса int — suspects и innocents, оба отсортированы по возрастанию. Верните новый слайс со всеми значениями suspects, которых нет в innocents, сохраняя исходный порядок.
Требование: O(n+m) по времени. Входные слайсы не изменять.
Примеры:
suspects=[1,2,3,4,5],innocents=[2,4]→[1,3,5]suspects=[3,80,123,421,936],innocents=[80,936]→[3,123,421]
func filter(suspects, innocents []int) []int {
// ваш код здесь
return nil
}Допишите реализацию.
Постройте множество map[int]struct{} из innocents (значение нулевого размера означает только членство, без полезной нагрузки). Пройдите range suspects, добавляя каждое значение, которого нет в множестве по comma-ok — O(n+m) по времени, O(m) по памяти. Поскольку оба входа отсортированы, слияние двумя указателями даёт альтернативу с O(1) памяти.
- ✗Сканировать
innocentsна каждого suspect и считать это O(n) вместо O(n·m) - ✗Изменять
suspectsна месте черезappend, портя слайс вызывающего - ✗Строить множество из
suspects, теряя исходный порядок и дубликаты
- →Оба входа отсортированы — как слияние двумя указателями уменьшит память до O(1)?
- →Почему для множества членства предпочесть
map[int]struct{}, а неmap[int]bool?
Задача
Вернуть значения suspects, отсутствующие в innocents, сохранив порядок.
func filter(suspects, innocents []int) []int {
skip := make(map[int]struct{}, len(innocents)) // множество членства
for _, v := range innocents {
skip[v] = struct{}{}
}
result := make([]int, 0, len(suspects))
for _, v := range suspects {
if _, innocent := skip[v]; innocent {
continue
}
result = append(result, v)
}
return result
}Как это работает
Сначала собираем innocents в множество map[int]struct{}. struct{} занимает ноль байт — это идиоматичный способ сказать «мне нужно только наличие ключа, не значение».
Затем один проход по suspects: если значение есть в множестве (comma-ok _, innocent := skip[v]), пропускаем его, иначе дописываем в result. Каждый элемент обрабатывается один раз с O(1)-поиском, поэтому общая сложность — O(n+m) по времени и O(m) по дополнительной памяти.
Почему именно result = append(result, v): append возвращает новый заголовок слайса (он может указывать на перевыделенный массив, когда ёмкость исчерпана), поэтому его результат обязательно присваивать обратно. Предвыделение make([]int, 0, len(suspects)) убирает повторные перевыделения. Входные слайсы при этом не изменяются.
⚠️ Вход отсортирован, поэтому есть альтернатива двумя указателями с O(1) памяти — она не строит множество, а синхронно идёт по обоим слайсам.
