1089. Duplicate Zeros #

题目 #

给定长度固定的整数数组 arr，将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注：不要在超过该数组长度的位置写入元素。对输入数组原地修改，不要从函数返回任何值。

思路 #

双指针 #

代码 #

双指针 #

class Solution {
    public void duplicateZeros(int[] arr) {
        /** 1. 由于复写零的存在，只需要不超过arr.length个原始数组元素即可将arr填满，首先确定需要多少个元素将arr填满 */
        int sum = 0, ptr = -1;
        while (sum < arr.length) {
            ptr++;
            if (arr[ptr] == 0) sum += 2;
            else dum += 1;
        }
        /** 2. sum的最终取值存在arr.length和arr.length+1两种情况 */
        /** 3. 从后向前填充数组 */
        for (int i = arr.length - 1; ptr > -1; ) {
            if (arr[ptr] == 0 && sum <= arr.length) {
                arr[i] = arr[i-1] = 0;
                i -= 2;
            }
            else {
                sum -= 1;
                arr[i] = arr[ptr];
                i -= 1;
            }
            ptr -= 1;
        }
    }
}