1. 重复0 - Duplicate Zeros

【双指针】

Problem Link

给你一个长度固定的整数数组 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%的用户

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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)$