数组 - 移动零

题目

https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/28/

个人解法

测试用例数(个) 执行用时(ms) 战胜
21 96 98.75%
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    var unZeroIndex = 0;
    
    for (var i = 0 ; i < nums.length ; i++) {
        if (nums[i] !== 0) {
            nums[unZeroIndex] = nums[i];
            unZeroIndex++;
        }
    }

    for (var i = nums.length - 1 ; i >= unZeroIndex ; i--) {
        nums[i] = 0;
    }
    
    return nums;
};

最快解法

测试用例数(个) 执行用时(ms) 战胜
21 64 100%
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    var zeroCount = 0;
    for(var i=0; i<nums.length; i++){
       if(nums[i]==0){
           zeroCount ++;
       }else if(zeroCount>0){
           nums[i-zeroCount]=nums[i];
           nums[i] = 0;
       }
    }
};

分析

「个人解法」时间复杂度为 O(2n),「最快解法」时间复杂度为 O(n)。特别是当数组全为零时,「个人解法」性能最差。

「最快解法」是将非零元素与第一个零元素进行交换。分解过程如下,以 [0,1,0,3,12] 为例:


[0,1,0,3,12]

--> 0,1交换

[1,0,0,3,12]

--> 0,3交换

[1,3,0,0,12]

--> 0,12交换

[1,3,12,0,0]

-->
*****
Written by Zheng Yu on 13 May 2019