面试官再问移动零算法题，我就这么答！

算法面试中，“移动零”这道题出现的频率可不低。今天咱们就花一分钟时间，把这道题彻底搞懂，面试的时候就轻松了。在正式解题前，先回顾两个数组操作的基础知识，如果已经熟悉的话，可以直接跳过这部分。

一、前置知识

（一）splice()方法

array.splice(start, deleteCount, item1, item2, ...)，它主要用来修改数组内容，能删除、替换或者添加元素，而且会直接改变原始数组。这里面start是必填的，表示从数组的哪个位置开始修改；deleteCount可选，用来指定要删除的元素个数；item1, item2, ...也是可选的，是准备添加到数组里的元素。这个方法会返回一个包含被删除元素的数组，如果没有删除元素，就返回空数组。

（二）push()方法

array.push(item1, item2, ...)，它的作用是把一个或多个元素添加到数组末尾，然后返回修改后数组的新长度。

二、题目详情

题目要求给定一个数组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之间，并且还有进阶要求，就是尽量减少操作次数。

三、解题思路与方法

（一）本人错误解法及原因分析

var moveZeroes = function(nums) { let count = 0; for(let i=0;i<nums.length;i++){ if(nums[i]===0){ nums.splice(i,1); count++; } } for(let i=0; i<count;i++){ nums.push(0) } return nums; };

看着好像能实现功能，但其实有问题。首先，在循环里用splice(i, 1)删除元素会导致数组索引错乱。删除一个元素后，数组长度变小，后面元素的索引会往前移，这样就可能跳过一些元素没处理，极端情况下还会出现越界访问的问题。其次，虽然是在原数组上修改，但用splice操作涉及数组重构，严格来说不算最高效的原地操作。

（二）正确题解一

/** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */ var moveZeroes = function(nums) { let insertPos = 0; // 第一次遍历：将所有非零元素移动到数组的前面 for (let i = 0; i < nums.length; i++) { if (nums[i]!== 0) { nums[insertPos] = nums[i]; insertPos++; } } // 第二次遍历：将数组剩余的位置填充为0 while (insertPos < nums.length) { nums[insertPos] = 0; insertPos++; } };

这个方法的思路是先把非零元素都挪到数组前面，再把剩下的位置用零填满。具体操作分两步：第一步，遍历数组，用insertPos记录下一个要插入非零元素的位置，遇到非零元素就把它放到nums[insertPos]，然后insertPos往后移；第二步，等遍历完，从insertPos开始到数组末尾，把这些位置都设为0。

（三）正确题解二（最优题解）

function moveZeroes(nums) { if (!nums || nums.length === 0) { return; } let left = 0; for (let right = 0; right < nums.length; right++) { if (nums[right]!== 0) { if (left!== right) { nums[left] = nums[right]; nums[right] = 0; } left++; } } }

这种解法用了两个指针left和right，left指向非零元素该放的位置，right用来遍历数组。right遇到非零元素，就把它移到left的位置，然后把right原来的位置设为0。这里有个优化点，就是只有当left和right不相等的时候才进行交换，避免了不必要的操作。相比第一种正确解法，它只需要一次遍历，还减少了交换次数，空间复杂度是O(1)，更高效。

咱们来看个实例，假设初始数组是[0, 2, 0, 3, 1, 0, 4] ，一开始left和right都指向索引0。right从左往右遍历，遇到0就跳过，遇到非零元素就看left和right是不是同一个位置，不是的话就交换，然后left右移。遍历完，非零元素就都在前面，零在末尾了。