Дано: целочисленный массив nums, переместите все 0 в его конец, сохранив относительный порядок ненулевых элементов.
Обратите внимание, что вы должны сделать это на месте, не создавая копию массива.
Пример 1:
Вход: nums = [0,1,0,3,12]
Выход: [1,3,12,0,0]
Пример 2:
Вход: nums = [0]
Выход: [0]
Ограничения:
1 <= nums.length <= 10^4
-2^31 <= nums[i] <= 2^31 - 1
Решения
1) Использования remove(не pop - его нельзя использовать в цикле)
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
for i in nums:
if i == 0:
nums.remove(0)
nums.append(0)
Если видим нулевой элемент, удаляем, и прибавляем его в конец.
Временная сложность: цикл даёт O(n), remove дает O(n) - итог O(n^2)
Пространственная сложность: O(1)
2) Использование указателя
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
j = 0
for i in nums:
if i != 0:
i[j] = i
j += 1
for i in range(j, len(nums)):
nums[i] = 0
Свернём алгоритм в один цикл.
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
j = 0
for i in range(len(nums)):
if nums[i] != 0 and nums[j] == 0:
nums[j], nums[i] = nums[i], nums[j]
if nums[j] != 0:
j+= 1
И для закрепления без меньших допущений:
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
i = 0
for j in range(len(nums)):
if (nums[j] != 0):
nums[i], nums[j] = nums[j], nums[i]
i += 1
Вводим вспомогательную переменную, проходим по циклу, если переменная не равна 0, то вставляем значение этой переменной, в массив под индексам вспомогательной переменной.
Временная сложность: цикл даёт O(n)
Пространственная сложность: переменная O(1)
