283.move-zeroes.md

题目地址

https://leetcode.com/problems/move-zeroes/description/

题目描述

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

思路

如果题目没有要求modify in-place 的话，我们可以先遍历一遍将包含0的和不包含0的存到两个数字， 然后拼接两个数组即可。 但是题目要求modify in-place， 也就是不需要借助额外的存储空间，刚才的方法 空间复杂度是O(n).

那么如果modify in-place呢？ 空间复杂度降低为1。

我们可以借助一个游标记录位置，然后遍历一次，将非0的原地修改，最后补0即可。

关键点解析

无

代码

/*
 * @lc app=leetcode id=283 lang=javascript
 *
 * [283] Move Zeroes
 *
 * https://leetcode.com/problems/move-zeroes/description/
 *
 * algorithms
 * Easy (53.69%)
 * Total Accepted:    435.1K
 * Total Submissions: 808.3K
 * Testcase Example:  '[0,1,0,3,12]'
 *
 * Given an array nums, write a function to move all 0's to the end of it while
 * maintaining the relative order of the non-zero elements.
 * 
 * Example:
 * 
 * 
 * Input: [0,1,0,3,12]
 * Output: [1,3,12,0,0]
 * 
 * Note:
 * 
 * 
 * You must do this in-place without making a copy of the array.
 * Minimize the total number of operations.
 * 
 */
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let index = 0;
    for(let i = 0; i < nums.length; i++) {
        const num = nums[i];
        if (num !== 0) {
            nums[index++] = num;
        }
    }

    for(let i = index; i < nums.length; i++) {
        nums[index++] = 0;
    }
};