Алгоритмы с нуля
Работа на месте
Нужно переставить массив — развернуть его, убрать элементы, сдвинуть нули в конец. Лёгкий путь: построить новый выходной массив, O(n) памяти. Сложный путь: переставить ячейки исходного массива прямо, используя только несколько указателей и временных переменных. O(1) дополнительной памяти. Сложный путь называют модификацией на месте, и это важно, когда память дефицитна или датасет огромен.
После урока ты сможешь объяснить, что значит “на месте” (переставка используя O(1) дополнительной памяти), узнавать задачи, что разрешают на-месте решения, кодировать три основных приёма (своп, сжатие указателем записи и разворот двумя противоположными указателями), разобраться в трейдоффе память-сложность и увидеть, почему на-месте алгоритмы уничтожают исходный массив.
Модификация на месте означает переставку массива перезаписывая его собственные ячейки, используя только O(1) дополнительной памяти (несколько указателей и временных переменных). Альтернатива — построение нового выходного массива — стоит O(n) дополнительной памяти.
Контраст: наивный против на-месте
Предположим, хочешь убрать все нули из [1, 0, 2, 0, 3, 0, 4] и сжать массив.
Наивный подход:
const result = [];
for (const x of arr) {
if (x !== 0) result.push(x);
}
// result = [1, 2, 3, 4], но мы создали новый массив (O(n) память)На-месте подход:
let write = 0; // Указатель: куда писать следующий сохранённый элемент
for (let i = 0; i < arr.length; i++) {
if (arr[i] !== 0) {
arr[write] = arr[i]; // Перезапиши на месте
write++;
}
}
// arr[0..write-1] = [1, 2, 3, 4], новый массив не создан (O(1) память)Оба дают одинаковый логический результат; один использует O(n) память, другой O(1).
Почему на-месте важно?
- Большие датасеты: 1 ГБ массива, выделить ещё 1 ГБ дорого.
- Лимиты памяти: Встроенные системы или облачные функции с тугим бюджетом.
- Сохранение ввода: Иногда ты хочешь сохранить исходный и платишь память. На-месте уничтожает его.
Три основных на-месте приёма
1. Своп
Обмен двух ячеек напрямую:
[arr[i], arr[j]] = [arr[j], arr[i]]; // Своп в одну строкуПрименяется в: развороте массива, переставке по чётности (чётные потом нечётные), внутри-месте сортировке.
2. Приём указателя записи
Указатель (write) отмечает, куда должен идти следующий сохранённый элемент. Указатель сканирования (i) движется по массиву. Когда сканирование находит хранимый, перезапиши в позицию write и продвинь write.
let write = 0;
for (let i = 0; i < arr.length; i++) {
if (condition(arr[i])) {
arr[write] = arr[i];
write++;
}
}Применяется в: удалении дубликатов (из урока 03), удалении целевого значения, фильтрации.
3. Разворот двумя противоположными указателями
Используй противоположные концы (из урока 03), своп концов, двигайся внутрь:
let left = 0, right = arr.length - 1;
while (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}Применяется в: развороте массива или строки на месте.
Цена: на-месте уничтожает ввод
На-месте алгоритм изменяет исходный массив. Если нужны и исходный и результат, скопируй до вызова алгоритма. Это трейдофф: O(1) дополнительная память ценой уничтожающегося ввода.
Запрограммируем три классические на-месте задачи.
1. Развернуть массив на месте (своп двумя противоположными указателями):
function reverseInPlace(arr) {
let left = 0, right = arr.length - 1;
while (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}
}2. Убрать целевое значение на месте (указатель записи):
function removeValue(arr, val) {
let write = 0;
for (let i = 0; i < arr.length; i++) {
if (arr[i] !== val) {
arr[write] = arr[i];
write++;
}
}
return write; // Новая длина (элементы что сохранить)
}3. Сдвинуть все нули в конец на месте (указатель записи):
function moveZeros(arr) {
let write = 0;
// Первый проход: сожми ненулевые в начало
for (let i = 0; i < arr.length; i++) {
if (arr[i] !== 0) {
arr[write] = arr[i];
write++;
}
}
// Второй проход: заполни остальное нулями
while (write < arr.length) {
arr[write] = 0;
write++;
}
}Запусти эти функции:
Проследим убрать значение на [1, 0, 2, 0, 3, 0, 4] убирая 0:
1
function removeValue(arr, val) {
2
let write = 0;
3
for (let i = 0; i < arr.length; i++) {
4
if (arr[i] !== val) {
5
arr[write] = arr[i];
6
write++;
7
}
8
}
9
return write;
10
}
Теперь проследим разворот на месте на [1, 2, 3, 4, 5]:
1
function reverseInPlace(arr) {
2
let left = 0, right = arr.length - 1;
3
while (left < right) {
4
[arr[left], arr[right]] = [arr[right], arr[left]];
5
left++;
6
right--;
7
}
8
}
| Задача | Время | Память (ввод) | Память (дополнительно) | Заметки |
|---|---|---|---|---|
| Развернуть массив на месте | O(n) | O(n) | O(1) | Два указателя своп; только left и right переменные |
| Убрать значение на месте | O(n) | O(n) | O(1) | Указатель записи + указатель сканирования; новый массив нет |
| Сдвинуть нули в конец на месте | O(n) | O(n) | O(1) | Два прохода: сжатие, потом заполнение |
| Убрать значение (построить новый массив) | O(n) | O(n) | O(n) | Создаёт новый выходной массив (не на-месте) |
Почему это лучше наивного подхода?
Наивное удаление массива строит свежий массив (O(n) дополнительная память). Удаление на-месте перезаписывает исходный, используя только указатель записи (O(1) дополнительная память).
Для маленьких массивов разница ничтожна. Для 1 ГБ массива выделить ещё 1 ГБ запрещённо.
Трейдофф память-время:
- На-месте: O(1) дополнительная память, но уничтожает ввод.
- Наивный (построить новый): O(n) дополнительная память, но ввод безопасен.
Выбирай по тому, можешь ли позволить потерять исходный.
Почему на-месте алгоритм убрать значение использует указатель записи?
Какова дополнительная память сложность разворота массива на месте двумя указателями?
После вызова removeValue([1, 0, 2, 0, 3], 0), какую длину возвращает функция?
Когда запускаешь на-месте алгоритм, что происходит с исходным массивом?
Приём указателя записи наиболее полезен когда:
Частая ошибка
Забыть что на-месте алгоритмы уничтожают ввод. Ты вызываешь removeValue(myArray, 5) думая что позже можешь ещё использовать myArray. Но алгоритм изменяет myArray напрямую. Если нужен был исходный, надо копировать сначала: const backup = [...myArray]; removeValue(myArray, 5);. Это частая ошибка в интервью и боевом коде.
Граничные случаи
Пустые или однородные массивы. Если массив пуст, цикл не запускается и write остаётся 0 (или функция возвращает 0). Если массив одного элемента и разворачиваешь или убираешь значение, указатели встречаются или проходят мимо сразу, массив неизменен. Оба случая обрабатываются верно.
Главное преимущество на-месте алгоритма в сравнении с построением нового выходного массива?
Модификация на месте переставляет массив без построения нового, используя только O(1) дополнительную память (несколько указателей и переменных).
Ключевые факты:
-
Своп: Прямой обмен ячеек используя
[a, b] = [b, a](или временную переменную). Применяется в разворотах и переставках. -
Приём указателя записи: Указатель отмечает куда писать следующий сохранённый элемент. Указатель сканирования движется по массиву. Когда сканирование находит хранимый, пиши его в позицию write и продвинь write. Применяется к фильтрации, удалению дубликатов и сжатию.
-
Разворот двумя противоположными указателями: Противоположные концы своп и движение внутрь. O(n) время, O(1) дополнительная память.
-
Трейдофф: На-месте экономит память но уничтожает исходный массив. Если нужны оба, скопируй сначала.
-
Когда это важно: Большие датасеты, лимиты памяти, встроенные системы. Для маленьких массивов экономия памяти ничтожна.
Дальше увидишь идеи на-месте расширенные на связные списки (где структура уже “на месте”) и на алгоритмы сортировки что обещают O(log n) или O(1) дополнительную память.