NOTES · 学习笔记
移动零:快慢指针各自干什么
题目
先看一下什么是指针:指针是一个用来记录当前位置的变量。这道题我们应该定义一个双指针——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++
}
}