[2022-06-17]1089. 复写零👋数组👋双指针

[webVueBlog]

题目链接: https://leetcode-cn.com/problems/duplicate-zeros

难度: Easy
标签: 数组 双指针

[dreamjean]

1089. 复写零

Description

Difficulty: 简单

Related Topics: 数组, 双指针

给你一个长度固定的整数数组 arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。

要求：请对输入的数组 **就地 **进行上述修改，不要从函数返回任何东西。

示例 1：

输入：[1,0,2,3,0,4,5,0]
输出：null
解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

示例 2：

输入：[1,2,3]
输出：null
解释：调用函数后，输入的数组将被修改为：[1,2,3]

提示：

1. 1 <= arr.length <= 10000
2. 0 <= arr[i] <= 9

Solution

方法一：利用 splice 的特性

• 在每个 0 的位置插入一个 0
• 同时强出最后个元素
• 因为增加了一个元素，因此 i 前进一格

Language: JavaScript

/**
 * @param {number[]} arr
 * @return {void} Do not return anything, modify arr in-place instead.
 */
var duplicateZeros = function(arr) {
    for (let i = 0; i < arr.length; i++) {
        if (!arr[i]) {
            arr.splice(i, 0, 0);
            arr.pop();
            i++;
        }
    }
};

方法二： 双指针

• 先统计出所有 0 的个数 countZero
• j 为原数组的长度 + 0 的总数
• 当 j 小于原数组的长度时，j 对应原数组 i 的位置
• 反向遍历原数组，逐步将元素分配到新的位置中

/**
 * @param {number[]} arr
 * @return {void} Do not return anything, modify arr in-place instead.
 */
var duplicateZeros = function(arr) {
    const n = arr.length;
    let cnt = 0;

    for (let num of arr) {
        if (!num) cnt++;
    }

    let j = n + cnt;
    for (let i = n - 1; i >= 0; --i) {
        if (--j < n) arr[j] = arr[i];
        if (!arr[i] && --j < n) arr[j] = 0;    
    }
};