Ссылка на задачу — 2460. Apply Operations to an Array.
📝 Описание задачи
Дан массив nums, состоящий из неотрицательных целых чисел. Нужно последовательно выполнить следующие операции:
- Для каждого валидного
i (в порядке возрастания):
- eсли
nums[i] == nums[i + 1], удвоить nums[i] и заменить nums[i + 1] на 0.
- После всех операций сдвинуть все нули в конец массива, сохраняя порядок оставшихся чисел.
- Вернуть изменённый массив.
💡 Идея
Решение можно выполнить за один проход, используя два указателя (read и write):
- Читаем массив и объединяем соседние одинаковые элементы.
- Перемещаем ненулевые элементы в начало массива.
- Оставшиеся ячейки заполняем нулями.
Такой подход позволяет изменять массив на месте, не используя дополнительную память.
📌 Детали подхода
- Используем два указателя (
read и write):
read проходит по массиву.write отслеживает следующую позицию для ненулевых чисел.
- Если текущий и следующий элементы равны → объединяем их и перемещаем в
nums[write].
- Если числа разные → просто перемещаем
nums[read] в nums[write].
- После обработки всех чисел, оставшиеся ячейки заполняем нулями.
⏳ Асимптотика
- Временная сложность:
O(n), так как массив обрабатывается ровно один раз.
- Дополнительная память:
O(1), так как изменения вносятся непосредственно в массив.
🔹 Оптимальное решение без лишних операций и копирования данных!
💻 Исходный код
impl Solution {
pub fn apply_operations(mut nums: Vec<i32>) -> Vec<i32> {
let mut write = 0;
let n = nums.len();
// Stage 1: Apply merge operations and compact nonzero values
let mut read = 0;
while read < n {
if nums[read] != 0 {
if read + 1 < n && nums[read] == nums[read + 1] {
nums[write] = 2 * nums[read];
read += 1; // Skip the next element as it's merged
} else {
nums[write] = nums[read];
}
write += 1;
}
read += 1;
}
// Stage 2: Fill remaining positions with zeros
nums[write..].fill(0);
nums
}
}
Tags: #rust #algorithms