LeetCode 热题 100 之第4题 移动零（JavaScript篇）

LeetCode 热题 100 之第4题“移动零”要求将数组中的零移动到数组的末尾，同时保持非零元素的相对顺序不变，JavaScript 解决方案通常使用双指针技巧，一个指针遍历数组，另一个指针记录非零元素应放置的位置，遍历过程中，将非零元素移动到正确位置，并在最后填充零，这种方法时间复杂度为 O(n)，空间复杂度为 O(1)，高效且简洁，通过此题，可以锻炼算法思维及编程能力。

LeetCode 热题 100 之第4题：移动零（JavaScript篇）

LeetCode 热题 100 是编程练习中的经典系列，每一题都经过精心挑选，旨在帮助开发者提升算法和编程能力，第4题“移动零”是一道非常经典的题目，要求将数组中的零移动到数组的末尾，同时保持非零元素的相对顺序不变，本文将详细介绍这道题的解题思路，并给出详细的 JavaScript 实现代码。 描述

给定一个数组 nums，编写一个函数将数组中的零移动到数组的末尾，同时保持非零元素的相对顺序不变，对于输入数组 [0, 1, 0, 3, 12]，输出应为 [1, 3, 12, 0, 0]。

解题思路

要解决这个问题,我们可以使用双指针的方法，具体步骤如下：

1. 定义两个指针,left 和 right，初始时都指向数组的第一个元素。
2. 遍历数组,当 right 指针遇到非零元素时，将其与 left 指针所指向的元素交换位置，并将 left 指针右移一位。
3. 当 right 指针遇到零时，不执行交换操作，只将 right 指针右移一位。
4. 继续上述步骤直到 right 指针遍历完整个数组。

这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)，非常高效。

实现代码

下面是详细的 JavaScript 实现代码：

/**
 * @param {number[]} nums
 * @return {void} Modify the input array in place.
 */
var moveZeroes = function(nums) {
    let left = 0; // 定义左指针
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] !== 0) {
            // 如果右指针指向的元素不是零，则与左指针指向的元素交换位置
            [nums[left], nums[right]] = [nums[right], nums[left]];
            left++; // 左指针右移一位
        }
    }
};

测试用例

为了验证上述代码的正确性,我们可以编写一些测试用例：

// 测试用例1：基本功能测试
let nums1 = [0, 1, 0, 3, 12];
moveZeroes(nums1);
console.log(nums1); // 输出: [1, 3, 12, 0, 0]
// 测试用例2：空数组测试
let nums2 = [];
moveZeroes(nums2);
console.log(nums2); // 输出: []（空数组）
// 测试用例3：全零数组测试
let nums3 = [0, 0, 0, 0, 0];
moveZeroes(nums3);
console.log(nums3); // 输出: [0, 0, 0, 0, 0] （没有变化）
// 测试用例4：全非零数组测试
let nums4 = [1, 2, 3, 4, 5];
moveZeroes(nums4);
console.log(nums4); // 输出: [1, 2, 3, 4, 5] （没有变化）

优化与扩展

上述解法已经足够高效,但如果需要进一步优化或处理更复杂的场景，可以考虑以下几点：

1. 原地修改：上述解法已经实现了原地修改，没有使用额外的空间，这是通过双指针和数组元素交换实现的，如果不需要返回新数组，而是直接修改原数组，这种方法非常合适。

2. 使用额外数组：虽然题目要求原地修改，但有时候为了简化代码逻辑，也可以使用一个额外的数组来存储结果，最后再复制回原数组，这种方法在需要保留原数组不变的情况下尤其有用。

   var moveZeroesUsingExtraArray = function(nums) {
       let result = []; // 使用额外数组存储结果
       for (let i = 0; i < nums.length; i++) {
           if (nums[i] !== 0) {
               result.push(nums[i]); // 将非零元素添加到结果数组中
           } else {
               result.push(0); // 将零元素也添加到结果数组中（但位置在最后）
           }
       }
       return result; // 返回结果数组（如果需要返回新数组）或直接赋值给原数组（如果需要原地修改）
   };

   注意：这种方法会返回一个新的数组而不是修改原数组，如果需要修改原数组，可以在函数最后一步将结果赋值给原数组：nums.length = 0; nums.push(...result);，但这样会增加时间复杂度为 O(n)，因为需要清空原数组并重新赋值，在大多数情况下，还是推荐使用双指针的原地修改方法。

3. 处理负数与小数：上述解法对负数和小数同样适用，因为题目没有限制输入元素的类型或范围，只要元素不是零，就会保留其相对顺序，如果需要考虑其他特殊情况（如非常大的数字或非常小的数字），可以在代码中增加相应的处理逻辑，但一般情况下，这些特殊情况不会影响算法的正确性。