LeetCode 热题 100-----4. 移动零

一、题目解析题目要求给定一个数组C中叫vectorPython中叫list把所有0移动到数组末尾非零元素的相对顺序不能改变例如输入[1,3,12]移动后仍是1→3→12的顺序原地修改不能创建新数组必须直接修改原数组示例输入[0,1,0,3,12]→ 输出[1,3,12,0,0]输入[0]→ 输出[0]二、必备前置知识为什么原地修改重要在编程中处理数组或列表时创建新数组会占用额外的内存空间。这就像你在家里整理衣柜时如果买个新衣柜来存放衣服虽然整洁了但浪费了空间和钱。原地修改则直接在原数组上操作节省内存效率更高。专业解释原地修改的算法通常只使用常数级别的额外空间这意味着空间复杂度为$O(1)$。无论数组有多大比如有1000个元素或10000个元素算法只使用几个固定变量如指针而不需要开辟新数组。这在大数据处理中非常关键能避免内存溢出。类比理解想象你在整理书架上的书。原地修改就像直接在书架上移动书本不需要买新书架而创建新数组就像租个新书架来放书整理完再搬回来既麻烦又占地方。另一个例子超市收银时收银员慢指针直接在收银台处理商品顾客快指针递送商品整个过程高效有序。核心思想双指针法是实现原地修改的常用技巧。它用两个变量指针协作慢指针slow标记目标位置比如存放非零元素的地方。它移动得慢只在需要时更新位置。快指针fast遍历整个数组快速寻找符合条件的元素如非零值。它移动得快扫描所有元素。深入理解数据结构在C中的vectorvector是动态数组能自动调整大小如添加元素时扩容。使用引用传参如void func(vectorint nums)时函数内修改nums会影响外部原数组因为它传递的是原数组的引用避免了值拷贝复制整个数组。代码示例void modifyArray(vectorint nums) { // 加表示引用传递 nums[0] 100; // 直接修改原数组的第一个元素 }如果不加函数会创建副本修改不影响原数组。在Python中的列表list列表是可变对象函数内修改会直接影响原列表。类型注解如def func(nums: List[int]) - None只是提示参数类型不影响运行。代码示例def modify_list(nums: list[int]) - None: nums[0] 100 # 直接修改原列表无需返回新列表这里nums是原列表的引用修改后外部列表也会变。三、核心解题思路双指针法最优解一句话总结双指针法通过慢指针标记位置、快指针遍历数组实现原地移动元素高效且节省内存。分步拆解以移动零问题为例初始化设置慢指针slow 0指向数组起始位置这里将存放第一个非零元素。快指针遍历快指针fast从左到右扫描数组遇到非零元素将当前元素复制到slow位置然后slow右移slow 1。这就像收银员接收商品并放到正确位置。遇到零元素跳过不处理。fast继续移动但slow不动。补零操作遍历结束后从slow位置开始到数组末尾所有元素赋值为0。确保零元素被移到末尾。为什么这个方法高效它只在必要时复制元素非零值避免了多次移动或创建临时数组。空间复杂度为$O(1)$时间复杂度为$O(n)$n是数组长度非常高效。示例演示数组[0,1,0,3,12]步骤1fast在位置0元素是0零跳过。slow保持在0。数组状态[0,1,0,3,12]步骤2fast移动到位置1元素是1非零复制到slow位置0slow右移到1。数组状态[1,1,0,3,12]注意原位置1的值被覆盖但快指针会继续扫描。步骤3fast移动到位置2元素是0零跳过。slow保持在1。数组状态[1,1,0,3,12]步骤4fast移动到位置3元素是3非零复制到slow位置1slow右移到2。数组状态[1,3,0,3,12]位置1的值被更新为3。步骤5fast移动到位置4元素是12非零复制到slow位置2slow右移到3。数组状态[1,3,12,3,12]位置2的值被更新为12。步骤6遍历结束从slow位置3开始到末尾赋值为0。最终数组[1,3,12,0,0]示例演示步骤fast位置当前元素操作slow位置数组状态100跳过0[0,1,0,3,12]211赋值1[1,1,0,3,12]320跳过1[1,1,0,3,12]433赋值2[1,3,0,3,12]5412赋值3[1,3,12,3,12]6--补零-[1,3,12,0,0]四、完整可执行代码含主函数测试1. C 代码逐行注释#include iostream #include vector using namespace std; class Solution { public: void moveZeroes(vectorint nums) { // 慢指针标记非零元素存放位置 int slow 0; // 快指针遍历整个数组 for (int fast 0; fast nums.size(); fast) { if (nums[fast] ! 0) { // 发现非零元素 nums[slow] nums[fast]; // 复制到慢指针位置 slow; // 慢指针后移 } } // 将剩余位置补零从slow到末尾 for (int i slow; i nums.size(); i) { nums[i] 0; } } }; // 主函数支持用户自定义输入 int main() { vectorint nums; cout 请输入数组长度; int n; cin n; cout 请输入数组元素用空格分隔; for (int i 0; i n; i) { int num; cin num; nums.push_back(num); } Solution().moveZeroes(nums); // 调用移动函数 cout 移动后的结果; for (int num : nums) { cout num ; } return 0; }测试示例输入请输入数组长度5 请输入数组元素0 1 0 3 12输出移动后的结果1 3 12 0 02. Python 代码逐行注释from typing import List class Solution: def moveZeroes(self, nums: List[int]) - None: # 慢指针标记非零元素存放位置 slow 0 # 快指针遍历整个列表 for fast in range(len(nums)): if nums[fast] ! 0: # 发现非零元素 nums[slow] nums[fast] # 复制到慢指针位置 slow 1 # 慢指针后移 # 将剩余位置补零从slow到末尾 for i in range(slow, len(nums)): nums[i] 0 # 主函数支持用户自定义输入 if __name__ __main__: nums list(map(int, input(请输入数组元素用空格分隔).split())) Solution().moveZeroes(nums) # 调用移动函数 print(移动后的结果, end) for num in nums: print(num, end )测试示例输入请输入数组元素0 1 0 3 12输出移动后的结果1 3 12 0 0五、边界情况测试输入输出说明[0][0]单个零[1,0,2][1,2,0]零在中间[1,2,3][1,2,3]无零元素[][]空数组六、算法复杂度进阶知识时间复杂度$O(n)$两次独立遍历快指针遍历 补零总操作次数$2n$。空间复杂度$O(1)$仅使用slow、fast等常数变量满足原地修改要求。总结核心方法双指针法慢指针存非零快指针找非零。关键规则非零元素顺序不变原地修改空间复杂度$O(1)$