前言
这是一道LeetCode经典题目“移动零”。
题目要求：
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例：
输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]
方案一：splice与pop
通过分析题目可知，是要找到每一个0，然后将0移动到数组的末尾，同时要注意的是不复制数组，影响的是元素组。
Up Code ~ 上代码 ~
/** * @method moveZeroes * @description 移动零 - pop/splice * @param nums number[] * @returns void */ function moveZeroes1(nums: number[]): void { // 获取数组的长度 const len = nums.length; // 临界点判定 if (len === 0) return; // 用来记录已经挪动到后面的0元素的个数，尽量减少下面for循环执行的次数 let zeroLength = 0; // 遍历每一个元素 for (let i = 0; i < len - zeroLength; i++) { // 判断当前元素是否为0 if (nums[i] === 0) { // 将数组当前i索引位置的元素给移除 nums.splice(i, 1); // 这里一定要注意，如果splice移除了元素之后，在其后的所有元素都会往前走一步 // 比如移除的是索引0位置，原先索引1位置跑到了索引0位置，不进行处理的话，这个位置的元素就会被跳过 // 所以这里的i要进行--操作，重新再指向当前位置索引 i--; // 数组末尾添加0 nums.push(0); // 记录里被移动的0的元素个数 zeroLength++; } } }
功能测试：
const nums = [0, 1, 0, 3, 12]; moveZeroes1(nums); console.log(nums); // [1, 3, 12, 0, 0]
需求是满足了，但是这个是理想的方案吗？！
在方案一中，使用splice来切割数组，这是非常不理智的行为，每移除一个元素，在其后的所有元素都要向前移动，带来了时间复杂度O(n)O(n)O(n)
方案一的整体时间复杂度为：O(n2)O(n^2)O(n2)
有没有更优的方案呢？
方案二：双指针
定义变量j，永远指向nums中第一个0，在遍历nums时，遇到非0元素，则与当前0指引的位置进行元素交换，这样0就移动到了后面，非0元素移动到了前面。然后将j++指向下一个0的位置。
Up Code ~ 上代码 ~
/** * @method moveZeroes2 * @description 移动零 - 双指针 * @param nums number[] * @returns void */ function moveZeroes2(nums: number[]): void { // 获取数组长度 const len = nums.length; // 临界点判断 if (len === 0) return; // !!!!重点 --- 永远指向第一个0 // 初始值设置为 -1 let j = -1; // 遍历nums的每一个元素 for (i = 0; i < len; i++) { // 当遇到第1个0时，j还未赋值，进行初始赋值操作 if (nums[i] === 0 && j < 0) { j = i; } // 遇到非0元素，同时j已经指向了第一个0 if (nums[i] !== 0 && j >= 0) { // 数组结构，交换索引位置的值 [nums[i], nums[j]] = [nums[j], nums[i]]; // j索引向后移动一位，指向下一个0 // 这个位置建议在纸上自己画一下指针移动的效果，就很容易明白了 j++; } } }
时间复杂度：只执行了一次for循环，时间复杂度为O(n)O(n)O(n)
功能测试：
const nums2 = [0, 1, 0, 3, 12]; moveZeroes2(nums2); console.log(nums2); // [1, 3, 12, 0, 0]
性能比较
方案一的时间复杂度是O(n2)O(n^2)O(n2)，方案二的时间复杂度是O(n)O(n)O(n)，同时我们再加上实际效果测试比对下性能。
声明一个20W条数组的数组，包含很多0值和非0值
// 声明2个，方案2和方案1各用1个，避免影响 const nums1: number[] = []; for (let i = 0; i < 20 * 20000; i++) { i % 10 === 0 ? nums1.push(0) : nums1.push(i); } const nums2: number[] = []; for (let i = 0; i < 20 * 20000; i++) { i % 10 === 0 ? nums2.push(0) : nums2.push(i); } console.time('moveZeros - splice'); moveZeroes1(nums1); console.timeEnd('moveZeros - splice'); console.time('moveZeros - doublePointer'); moveZeroes2(nums2); console.timeEnd('moveZeros - doublePointer');
上图
网络异常，图片无法展示
|
我们可以看到，性能差距特别大，方案二的双指针算法明显优于方案一！
