重复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 <= arr.length <= 10000
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


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)$

重复0 - Duplicate Zeros

Problem Link

Example:

Analysis

Solution

复杂度分析

相关文章：