JuniorКодЧастоЕщё не отвечали
Удаление нулей из вектора с сохранением порядка за O(n)
Удалите все нули из вектора целых чисел, сохранив относительный порядок остальных элементов.
Требования:
(это O(n²)).
- O(n) время, O(1) дополнительной памяти — не сдвигать хвост на каждом удалении
void removeZeros(std::vector<int>& v) {
// ваш код здесь
}Допишите реализацию.
Используйте индекс записи. Идите по вектору индексом чтения; для каждого ненулевого элемента копируйте его в позицию записи и продвигайте индекс записи. После прохода усеките вектор до индекса записи. Один проход, O(n) время, O(1) дополнительной памяти. Идиоматичная форма — erase-remove: v.erase(std::remove(v.begin(), v.end(), 0), v.end()).
- ✗Вызывать
eraseна каждый ноль, сдвигая хвост каждый раз и вырождаясь в O(n²) - ✗Обмен с концом, который удаляет нули, но ломает порядок оставшихся элементов
- ✗Забывать усечь/erase оставшийся хвост после уплотнения
- →Что
std::removeна самом деле делает с хвостом и почемуeraseвсё ещё нужен? - →Как вместо этого перенести все нули в конец, сохранив порядок ненулевых?
Оглавление
Задача
Удалите нули из вектора, сохранив порядок, за O(n) и O(1) памяти.
Решение
#include <vector>
#include <algorithm>
void removeZeros(std::vector<int>& v) {
size_t write = 0;
for (size_t read = 0; read < v.size(); ++read)
if (v[read] != 0) v[write++] = v[read]; // переносим ненулевые
v.resize(write); // усекаем хвост
}
// Идиоматичный вариант:
// v.erase(std::remove(v.begin(), v.end(), 0), v.end());Ключевые моменты
- Индекс записи уплотняет ненулевые элементы за один проход — порядок сохранён.
std::removeлишь сдвигает элементы; реально размер меняет последующийerase.- Поэлементный
eraseсдвигает хвост каждый раз и даёт O(n²).
Оглавление
