LeetCode-Go 题解：283. Move Zeroes——双指针原地移动零元素的三种变体

LeetCode-Go 题解283. Move Zeroes——双指针原地移动零元素的三种变体【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 283 题Move Zeroes移动零展开以 LeetCode-Go 仓库中 leetcode/0283.Move-Zeroes/README.md 为主体结合仓库内对应的 Go 实现 与 测试用例讲解如何在不借助额外数组的前提下用一趟扫描完成原地置换保持非零元素的相对顺序。读完本文你将掌握双指针快慢交换这一高频技巧并能顺带打通第 26、27、80 题的同源解法。题目描述Given an array nums, write a function to move all 0s to the end of it while maintaining the relative order of the non-zero elements.给定一个整数数组nums编写一个函数将所有的0移动到数组的末尾同时保持所有非零元素的相对顺序不变。示例Input: [0,1,0,3,12] Output: [1,3,12,0,0]题目附带的两个约束是这道题真正的考点必须原地in-place操作不允许复制一份数组尽量最小化总的操作次数Minimize the total number of operations。题目大意中文解读结合 leetcode/0283.Move-Zeroes/README.md 中的中文说明本题核心要求可概括为两点不能采用额外的辅助空间即空间复杂度必须控制在 O(1) 级别将数组中的所有0元素移动到末尾并且维持所有非0元素的相对位置不变。也就是说[0,1,0,3,12]处理后的结果必须是[1,3,12,0,0]1,3,12三者的先后次序不能被改变——这一点直接否定了先把非零挑出来、再整体排序之类的思路也决定了必须采用保持稳定性的原地算法。解题思路一趟扫描的 i、j 双指针交换README 给出的解题思路非常精炼这一题可以只扫描数组一遍不断的用 ij 标记 0 和非 0 的元素然后相互交换最终到达题目的目的。这里i是快指针负责遍历数组寻找非零元素j是慢指针标记下一个应该放置非零元素的位置。每一轮遇到非零元素时把nums[i]与nums[j]交换然后j前进一位。由于i恒不小于j交换操作只会把非零值向前搬运把0向后推移因此非零元素的相对顺序得到保持稳定所有0最终被挤到数组末尾全程只扫描一遍数组时间复杂度 O(n)空间复杂度 O(1)。仓库源码级实现解析仓库中的核心实现位于 leetcode/0283.Move-Zeroes/283. Move Zeroes.go完整代码如下package leetcode func moveZeroes(nums []int) { if len(nums) 0 { return } j : 0 for i : 0; i len(nums); i { if nums[i] ! 0 { if i ! j { nums[i], nums[j] nums[j], nums[i] } j } } }关键实现细节拆解空数组早退if len(nums) 0 { return }保证对空切片安全返回这与 gotest.sh 覆盖全仓库测试的运行方式配合避免空输入引发越界。i ! j的优化当i与j指向同一位置说明从j到i之间没有出现过0此时元素本就在正确的位置上交换自身毫无意义。显式跳过该分支减少了不必要的写操作正是题目最小化操作次数这一要求的直接体现。交换的等价性由于j i恒成立nums[j]在被交换前要么是0前面有零元素被跳过要么是j i时的自身因此交换不会破坏任何非零元素的相对次序。复杂度与正确性时间复杂度O(n)其中 n 为数组长度每个元素至多被访问一次空间复杂度O(1)只使用了一个额外的整型变量j稳定性非零元素顺序保持完全满足题意。测试用例与验证仓库为本题配备了 7 组表驱动测试见 leetcode/0283.Move-Zeroes/283. Move Zeroes_test.go覆盖了各种边界情况输入期望输出覆盖场景[1, 0, 1][1, 1, 0]非零元素中间夹一个零[0, 1, 0, 3, 0, 12][1, 3, 12, 0, 0, 0]连续多个零分散在数组中[0, 1, 0, 3, 0, 0, 0, 0, 1, 12][1, 3, 1, 12, 0, 0, 0, 0, 0]长零序列 多个非零元素[0, 0, 0, 0, 0, 0, 0, 0, 12, 1][12, 1, 0, 0, 0, 0, 0, 0, 0, 0]全零前缀[0, 0, 0, 0, 0][0, 0, 0, 0, 0]全零数组[1][1]单元素数组[][]空数组其中全零数组与空数组两个用例恰好验证了实现中的空输入早退与无零可移的幂等行为。测试采用 Go 标准库testing编写运行方式与仓库整体一致go test ./leetcode/0283.Move-Zeroes/ -v仓库根目录还提供了 gotest.sh用于对./leetcode/...下所有题目包一次性生成合法的覆盖率文件方便核对本题的覆盖情况。延伸与第 26、27、80 题的同源解法README 明确指出与这一题相近的题目有第 26 题第 27 题第 80 题。从源码结构看这四题共享同一套双指针原地重排的心法区别只在于判定条件与返回值第 26 题 Remove Duplicates from Sorted Array用last、finder两个指针去重把每个不重复的元素搬到数组前部返回新长度第 27 题 Remove ElementremoveElement(nums, val)把不等于val的元素全部前移j即新长度其跳过目标值、快慢指针交换的骨架与moveZeroes几乎逐行对应——moveZeroes可以看作val 0且把剔除的元素收拢到末尾的特例第 80 题 Remove Duplicates from Sorted Array II允许每个元素最多保留两个副本用slow、fast指针配合nums[slow-2] ! v判定思路同源但阈值不同。对照阅读这四份实现可以归纳出这一类数组原地重排题的通用套路一个快指针负责探测一个慢指针负责记录写入位置以某种规则决定哪些元素需要被跳过。掌握了 283 题的双指针交换其余三题基本可以举一反三。小结第 283 题是双指针技巧中最典型的入门题之一。LeetCode-Go 仓库给出的实现用最少的代码量满足了原地 一趟扫描 保持相对顺序 最小化操作次数的全部约束并通过 测试用例 覆盖了从空数组到全零数组的各类边界。建议读者在理解i、j交换逻辑后结合第 26、27、80 题的源码做对比练习把快慢指针原地重排固化成可迁移的解题肌肉记忆。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考