283. 移动零

Origin: LeetCode 283

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。要求原地操作，不使用额外空间。

示例

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

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

约束

• 1 <= nums.length <= 10
• -2^31 <= nums[i] <= 2^31 - 1

关键信息

• 原地操作，O(1) 空间
• 保持非零元素的相对顺序
• 双指针：一个写位置，一个遍历

Resolution

我的解法

function moveZeroes(nums: number[]): void {
    let left = 0
    for (let right = 0; right < nums.length; right++) {
        while (nums[right] !== 0 && right < nums.length) {
            nums[left] = nums[right]
            left++
            right++
        }
    }
    for (let i = left; i < nums.length; i++) {
        nums[i] = 0
    }
}

解题思路

双指针。left 记录下一个非零元素该放的位置，right 遍历数组。遇到非零就搬到 left 位置，left 和 right 同时前进。最后 left 之后的位全填 0。

踩坑

• while 里 right < nums.length 的判断放在后面，如果 nums[right] !== 0 先判断会越界。不过 for 循环已经限制了 right 范围，其实不需要 while，直接用 if 就行

更简洁的写法

function moveZeroes(nums: number[]): void {
    let left = 0
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] !== 0) {
            nums[left] = nums[right]
            left++
        }
    }
    for (let i = left; i < nums.length; i++) {
        nums[i] = 0
    }
}

复杂度

• 时间：O(n)
• 空间：O(1)