Переместите нули

Легкая

09 March 2024

Описание задачи #

Вам дан целочисленный массив nums. Переместите в нём все нули в конец, сохраняя относительный порядок ненулевых элементов.

Обратите внимание, что вы должны сделать это in-place, не копируя массив.

Ограничения #

Длина массива от 1 до 10000 элементов
Каждый элемент массива может принимать значение в диапазоне от -2³¹ до 2³¹ - 1

Примеры #

Входные данные: nums = [0,1,0,3,12]

Ответ: [1,3,12,0,0]
Входные данные: nums = [0]

Ответ: [0]

Решение #

Решение задачи крайне простое.

Нам нужно завести два индекса. Первый — обычный индекс i, который инкриминируется на каждой итерации. Второй firstZeroIndex — индекс первого нулевого элемента в массиве, который изначально равен 0.

Далее мы итерируемся по всем элементам массива и, как только встречаем ненулевой элемент, меняем его местами с нулем, который стоит под индексом firstZeroIndex. Дополнительно увеличиваем firstZeroIndex, если произошла перестановка.

Таким образом все нули будут «всплывать» в конец массива за один проход.

Реализация #

package main

func moveZeroes(nums []int) {
	for firstZeroIndex, i := 0, 0; i < len(nums); i++ {
		if nums[i] != 0 {
			nums[i], nums[firstZeroIndex] = nums[firstZeroIndex], nums[i]
			firstZeroIndex++
		}
	}
}

export const moveZeroes = (nums: number[]): void => {
	for (let firstZeroIndex = 0, i = 0; i < nums.length; i++) {
		if (nums[i] !== 0) {
			const temp = nums[i]
			nums[i] = nums[firstZeroIndex]
			nums[firstZeroIndex] = temp
			firstZeroIndex++
		}
	}
};

Оценка сложности #

По времени

Сложность O(n), так как мы итерируемся по всем элементам массива.

По памяти

Сложность O(1), так как мы не выделяем дополнительную память, зависящую от длины массива.

Оригинал задачи на Leetcode

Algorithmics