XTY的小站
记录技术笔记和技术博客

283. Move Zeroes

15 Jun 2024

283. Move Zeroes (easy) 移动零

题干

Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:

Input: nums = [0]
Output: [0]

Constraints:

Follow up: Could you minimize the total number of operations done?

解题思路

因为不能创建新数组，只能in place替换，所以空间复杂度只能用到O(1)。时间复杂度因为有循环，最低是O(n)。

那弄两个指针，一个遇零则停（非零则自增），一个按循环自增。当两个指针元素，一个为0，一个不为0时，则交换。这样时间复杂度是O(n)。

我的答案

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        zero_idx = 0
        for i in range(len(nums)):
            if nums[zero_idx] == 0 and nums[i] != 0:
                nums[zero_idx], nums[i] = nums[i], nums[zero_idx]

            if nums[zero_idx] != 0:
                zero_idx += 1