移动零

题目：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1：

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2：

输入: nums = [0]
输出: [0]

提示：

1 <= nums.length <= 104

-231 <= nums[i] <= 231 - 1

解题过程

思路

这道题要求将数组中的零移动到末尾，同时保持非零元素的相对顺序，并且要求在原地操作，不能复制数组。一个高效的方法是使用双指针技术。

解法：

可以使用两个指针，一个指针遍历数组寻找非零元素，另一个指针记录非零元素应该放置的位置。具体步骤如下：

1. 初始化指针：定义一个指针 k，用来标记非零元素应该放置的位置。
2. 遍历数组：用另一个指针遍历数组，遇到非零元素时，将其放到 k 指针的位置，并将 k 向后移动一位。
3. 处理零元素：遍历完成后，从 k 指针的位置开始到数组末尾填充零。

这种方法的时间复杂度是 O(n)，空间复杂度是 O(1)，符合题目要求。

代码：

class Solution {
public:void moveZeroes(vector<int>& nums) {int k = 0;  // 记录非零元素的存放位置// 遍历数组，找出所有非零元素并往前放for (int i = 0; i < nums.size(); ++i) {if (nums[i] != 0) {nums[k++] = nums[i];}}// 将剩余的位置填充零while (k < nums.size()) {nums[k++] = 0;}}
};

代码解释

• 初始化指针：int k = 0; 用于记录非零元素的存放位置。
• 遍历数组：for (int i = 0; i < nums.size(); ++i)，当遇到非零元素时，将其放在 k 指针的位置，并将 k 向后移动一位。
• 填充零：循环结束后，从 k 到数组末尾的位置填充零。

这种方法高效且简单，适合处理大规模数据，同时保持了原地操作的要求。