Удалите все нули из слайса целых на месте, вернув усечённый слайс
Реализуйте remove(in), удаляющую каждый 0 из слайса и возвращающую результат. Сделайте это на месте, не выделяя второй слайс. Требование: O(n) по времени, O(1) доп. памяти. Примеры: remove([]) → []; remove([0]) → []; remove([1,0,0,2]) → [1,2].
func remove(in []int) []int {
// ваш код здесь
return nil
}Допишите реализацию.
Используйте индекс записи j с нуля. Сканируйте индексом чтения i; когда in[i] != 0, копируйте его в in[j] и продвигайте j. После прохода первые j элементов — это ненулевые, поэтому верните in[:j]. Это уплотняет на месте за один проход — O(n) по времени и O(1) доп. памяти — и работает для пустого и полностью нулевого случаев.
- ✗Вырезать через
appendна каждый ноль, что даёт O(n²), а не O(n) - ✗Выделять новый слайс и называть это работой на месте
- ✗Забыть вернуть
in[:j]и вернуть весь слайс
- →Как заодно обнулить хвостовые элементы, чтобы освободить ссылки?
- →Как это уплотнение двумя указателями обобщить на удаление по предикату?
Решение
Два указателя в одном слайсе: i читает, j пишет. Копируем только ненулевые.
func remove(in []int) []int {
j := 0
for i := 0; i < len(in); i++ {
if in[i] != 0 {
in[j] = in[i]
j++
}
}
return in[:j]
}
// remove([]int{1, 0, 0, 2}) -> [1 2]Каждый ненулевой элемент сдвигается влево на свою итоговую позицию. После прохода первые j элементов — результат, и in[:j] отсекает хвост. Один проход — O(n) по времени; новый слайс не выделяется — O(1) доп. памяти.
⚠️ Частая ошибка — вырезать нули через append(in[:i], in[i+1:]...) в цикле: это O(n²), потому что каждый вырез сдвигает хвост.
