283 移动零

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

示例:

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

说明:

必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。

题解

1. 使用 lastIndexOf 从后向前查找，如果找到了就移动到最后。

TIP

执行用时：100 ms, 在所有 JavaScript 提交中击败了 27.04% 的用户
内存消耗：39.8 MB, 在所有 JavaScript 提交中击败了 25.51% 的用户

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let count = -1
    let lastZeroIdx = nums.lastIndexOf(0)
    // 只要找到了 0 
    while(lastZeroIdx > -1) {
        // 执行移动操作
        nums.push(nums.splice(lastZeroIdx, 1))
        // 从后向前查找，每找到一个则起始位置 +1
        lastZeroIdx = nums.lastIndexOf(0, count--)
    }

    return nums
};

• 时间复杂度： `O(n)`，n 指的是 0 的个数。
• 空间复杂度： `O(1)`，使用常数级别的空间。
• 最好情况： 一个 0 或者没有 0，则不执行循环操作，直接返回原数组。
• 最坏情况： 数组里全是 0，则需要依次从末尾遍历到开头。

2. 利用双指针，先把所有不为零的元素放到数组的开头，那么数组的长度减去不为零的个数，就是零的个数。

TIP

执行用时：84 ms, 在所有 JavaScript 提交中击败了 71.37% 的用户
内存消耗：39.8 MB, 在所有 JavaScript 提交中击败了 31.09% 的用户

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    const {length: l} = nums

    let count = 0
    for(let i of nums) {
        if(i) {
            // 如果不为 0，则把数字放在数组的开头
            nums[count] = i
            // 递增 idx
            count++
        }
    }
    // 剩下的即为要不全 0 的个数
    for(let j =count;j<l;j++) {
         nums[j] = 0
    }
    return nums
};

• 时间复杂度： `O(n)`，2 个循环。
• 空间复杂度： `O(1)`，使用常数级别的变量。
• 最好情况： 大部分的 0 在数组的末尾，即不需要太多的修改。
• 最坏情况： 数组里大部分是 0，且在数组的开头。