为什么我利用辅助数组和没有用辅助数组的空间复杂度相似？

来源：3-4 即使简单的问题，也有很多优化的思路

骡子不会飞

2021-04-25

var moveZeroes = function(nums) {
    if(!(nums instanceof Array)) return nums;
    if(nums.length <= 1) return nums;
    let i = 0; // i作为[0, nums.length)的指针
    let k = 0; // [0, k)区间中，均为非0元素，k作为辅助指针
    while(i < nums.length) {
        if(nums[i] !== 0) {
            nums[k++] = nums[i];
        }
        i++;
    }
    // [k, nums.length)区间的全为0
    while(k < nums.length) {
        nums[k++] = 0; 
    }
};

为什么我在leetcode submit这个算法的结果，是和利用了辅助数组：

var moveZeroes = function(nums) {
    if(!(nums instanceof Array)) return nums;
    if(nums.length <= 1) return nums;
    // [0...nums.length)区间，
    // 遍历所有非0元素加入nonZeroArr，
    // 然后将nonZeroArr填入nums数组，
    // 剩下的nums元素都用0覆盖。
    const nonZeroArr = []
    for(let i = 0, len = nums.length; i < len; i++) {
        if(nums[i]) nonZeroArr.push(nums[i]);
    }
    for(let i = 0, len = nonZeroArr.length; i < len; i++) {
        nums[i] = nonZeroArr[i];
    }
    for(let i = nonZeroArr.length; i < nums.length; i++) {
        nums[i] = 0;
    }
};

这个算法的空间消耗是差不多的？
前者是：Memory Usage: 40.2 MB
后者是：Memory Usage: 40.7 MB
感觉不到前者空间复杂度是O(1)啊

写回答

1回答