Задача с собеседования в eBay
Задача с собеседования в eBay
Дан целочисленный массив nums. Переместите все нули в его конец, сохранив при этом относительный порядок ненулевых элементов.
Обратите внимание, что необходимо сделать это in-place, без создания копии массива.
Пример 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Пример 2:
Input: nums = [0]
Output: [0]
Ограничения:
1 <= nums.length <= 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Используем метод двух указателей, идём по массиву в одном направлении слева направо:
l - позиция, куда нужно поставить следующее ненулевое число
r - проходит по всем элементам массива
Проходим по массиву указателем r:
если r указывает на ненулевой элемент, меняем его местами с элементом на позиции l и двигаем левый указатель.
После завершения итерации с индексом r:
- все элементы до l будут ненулевыми;
- все элементы от l до r включительно - нули.
Вывод результата не требуется. Решение соблюдает принцип in-place (работаем с исходным массивом) и сохраняет порядок ненулевых элементов.
Сложность
O(n) - по времени (проходим по массиву один раз)
O(1) - по памяти (используем две переменные, изменяем только исходный массив)
Код
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
l = 0
for r in range(len(nums)):
if nums[r] != 0:
nums[l], nums[r] = nums[r], nums[l]
l += 1
@algoses
Откликнуться в Telegram →
⚠️ Никогда не платите «за оформление» или «гарантию трудоустройства» — это признак мошенников. Работа ТРУ не несёт ответственности за содержание вакансии.
