LeetCode 283. 移动零

1. 题目描述

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

注意：必须在 原地 对数组进行操作，不得额外分配新数组。

示例

示例 1:

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

示例 2:

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

提示：

• 1 <= nums.length <= 10⁴
• -2³¹ <= nums[i] <= 2³¹ - 1

2. 解题思路

为了在原地移动数组中的零，我们可以使用双指针法：

• 核心思路：
  • 定义两个指针：
    1. cur：用于遍历数组。
    2. dest：记录当前非零元素的插入位置。
  • 在遍历过程中：
    • 如果 nums[cur] 为非零，则将其与 nums[dest] 交换，同时 dest 向前移动一位。
    • 如果 nums[cur] 为零，则跳过该元素。
  • 最终所有非零元素会移动到数组前部，dest 后的所有元素自动变为零。
• 数组区间划分：
  • [0, dest]：非零元素。
  • [dest + 1, cur - 1]：处理过的零元素。

此方法只需遍历数组一次，时间复杂度为 O(n)O(n)，且在原地完成操作，符合题目要求。

3. 算法代码

以下是 C++ 实现：

class Solution {
public:void moveZeroes(vector<int>& nums) {int n = nums.size();int dest = -1; // 初始化非零元素的插入位置for (int cur = 0; cur < n; ++cur) {if (nums[cur] != 0) { // 遇到非零元素时，交换到 dest 指针的位置swap(nums[++dest], nums[cur]);}}}
};

4. 题目总结

本题考察了数组的 原地操作 和 双指针技巧，关键在于：

1. 合理划分数组的区间。
2. 减少无效的数组元素操作。

总结

本题考察了数组的 原地操作 和 双指针技巧，关键在于：

1. 合理划分数组的区间。
2. 减少无效的数组元素操作。

通过双指针法，可以高效地解决“移动零”的问题，同时保证代码简洁易读。如果有其他问题或更优解法，欢迎交流讨论！