NOTES · 学习笔记

移动零:快慢指针各自干什么

LeetCode双指针 · 简单约 3 分钟

题目

先看一下什么是指针:指针是一个用来记录当前位置的变量。这道题我们应该定义一个双指针——i 作为快指针去遍历数组中的元素,j 作为慢指针去记录位置。示例:输入 nums = [0,1,0,3,12],输出 [1,3,12,0,0]。

思路是遍历所有元素,把非零元素更新到 j 的位置。比如现在 j 指向 0,i 指向 1:i 是非零元素,把 1 保存到 j 的位置上,数组变成 [1,1,0,3,12],j++ 来到第二个位置。i 继续走,指向 0,因为是零,j 不动还在第二个位置。i 来到 3,3 是非零元素,把 3 更新到 j 的位置,变成 [1,3,0,3,12],j++ 后来到第三个位置,i 来到了 12。12 是非零元素,更新到 j 的位置上,数组变成 [1,3,12,3,12]。

i 遍历完数组,所有非零元素已经按原来的顺序放到前面,j 指向第四个位置,也就是下标 3。接下来把后面的元素变为零:用 for 循环,当 j < len(nums) 时,把剩下的元素都变为零,完成。

func moveZeroes(nums []int) {
    j := 0
    for i := range nums {      // i遍历数组中的元素
        if nums[i] != 0 {      // 当i遍历到一个非零元素时
            nums[j] = nums[i]  // 更新一下位置,我们将i这个元素更新到j的位置上
            j++                // 更新完位置后,j往后移动一个位置
        }
    }
    for j < len(nums) {        // 所有非零元素位置已排好,j指向下一个应该放置元素的位置
        nums[j] = 0            // 我们将后面的元素更新为零
        j++
    }
}