You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

1089. 重复0 - Duplicate Zeros

. 1 min read

【双指针】

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

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

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

Example:

Example 1:

Input: [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Example 2:

Input: [1,2,3]
Output: [1,2,3]
Explanation: After calling your function, the input array is modified to: [1,2,3]

Note:

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

Analysis

遇见零需要重复,但不是覆盖!所以用两个指针即可,遇见零则暂时不移动

下面是一种实现方式,还可以考虑遇见零让结果数组走两步赋值0,但这样就要考虑越界

Solution

执行用时 :2 ms, 在所有Java提交中击败了100.00%的用户

内存消耗 :39.9 MB, 在所有Java提交中击败了100.00%的用户

class Solution {
    public void duplicateZeros(int[] arr) {
        /* 双指针 */
        int len = arr.length;
        int[] aux = arr.clone();

        int i = 0; // pointer for arr
        int j = 0; // pointer for aux        
        
        boolean isZero = false;
        for (i = 0; i < len; i++) {
            if (!isZero) {
                int tmp = aux[j];
                arr[i] = tmp;
                if (tmp == 0) {
                    isZero = true;
                }
                j++;
            } else {
                isZero = false;
                arr[i] = 0;
            }
        }
        return;
    }
}

复杂度分析

时间:$O(N)$

空间:$O(N)$