当前位置：首页 > news >正文

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

news 2026/7/14 16:07:02

一、题目解析

题目要求
给定一个数组（C++中叫vector，Python中叫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++中的vector：vector是动态数组，能自动调整大小（如添加元素时扩容）。使用引用传参（如void func(vector<int>& nums)）时，函数内修改nums会影响外部原数组，因为它传递的是原数组的引用，避免了值拷贝（复制整个数组）。代码示例：
```
void modifyArray(vector<int>& 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]）：

步骤1：fast在位置0，元素是0（零），跳过。slow保持在0。数组状态：[0,1,0,3,12]
步骤2：fast移动到位置1，元素是1（非零），复制到slow位置（0），slow右移到1。数组状态：[1,1,0,3,12]（注意：原位置1的值被覆盖，但快指针会继续扫描）。
步骤3：fast移动到位置2，元素是0（零），跳过。slow保持在1。数组状态：[1,1,0,3,12]
步骤4：fast移动到位置3，元素是3（非零），复制到slow位置（1），slow右移到2。数组状态：[1,3,0,3,12]（位置1的值被更新为3）。
步骤5：fast移动到位置4，元素是12（非零），复制到slow位置（2），slow右移到3。数组状态：[1,3,12,3,12]（位置2的值被更新为12）。
步骤6：遍历结束，从slow位置（3）开始到末尾，赋值为0。最终数组：[1,3,12,0,0]

示例演示

步骤	fast位置	当前元素	操作	slow位置	数组状态
1	0	0	跳过	0	`[0,1,0,3,12]`
2	1	1	赋值	1	`[1,1,0,3,12]`
3	2	0	跳过	1	`[1,1,0,3,12]`
4	3	3	赋值	2	`[1,3,0,3,12]`
5	4	12	赋值	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(vector<int>& 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() { vector<int> 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 0

2. 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=" ")

测试示例
输入：