283. Move Zeroes (Easy)

2020-06-22 约 547 字预计阅读 2 分钟次阅读

把数组中的 0 移到末尾

题目描述

如题，把数组中的 0 移到末尾

统计

版本	耗时	超越	内存	超越	更新时间
v 1.0.0	76ms	44.89%	36.9MB	22.65%	2020年06月22日20:17:00

想法 v 1.0.0

分析：把数组最终结果看成两个部分，一部分全是非 0，余下的尾部都是 0，先处理非 0，然后末尾补 0。

实现：题目中没有提到需要排序，所以只需要遍历一次原数组，把非 0 项从头开始重新插入，在末尾补 0，实现所谓的移动到末尾。

核心逻辑

使用下标 index 来记录非 0 项
遍历原数组，当元素非 0 时，把该元素赋值给 nums[index]，然后 index++
遍历结束后，如果 index < 原数组长度，则在末尾补上 nums.length - index 个 0

复杂度分析

时间复杂度

遍历了一次原数组， O(n)
末尾补零遍历， O(nums.length - index)
- 最差情况原数组都是 0，index === 0，即 O(n)
- 最好情况原数组都非 0, index === nums.length，即 O(0)

空间复杂度

只用了 1 个临时变量，所以是 O(1)级别

测试数据

[0,1,0,3,12]

[0,0,0]

[1,1,1]

AC 代码

2020年06月22日20:17:00

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26



/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    // 使用下标 `index` 来记录非 `0` 项
    var index = 0;
    /**
     * 遍历原数组，当元素非 `0` 时，把该元素赋值给 `nums[index]`， 然后 `index++`
     */
    for(var i = 0;i < nums.length;i++) {
        if(nums[i] !== 0) {
            nums[index] = nums[i];
            index++;
        }
    }
    /**
     * 遍历结束后，如果 `index` < 原数组长度，则在末尾补上 `nums.length - index` 个 `0`
     */
    while (index < nums.length) {
        nums[index] = 0;
        index++;
    }
};

目录