1089-复写零

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:30 2023-09-13 16:06:30 Updated    

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

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 **就地 **进行上述修改，不要从函数返回任何东西。

示例 1：

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

示例 2：

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

提示：

  • 1 <= arr.length <= 104
  • 0 <= arr[i] <= 9

方法一：双指针

思路与算法

首先如果没有原地修改的限制，那么我们可以另开辟一个栈来进行模拟放置：

<fig1,fig2,fig3,fig4,fig5,fig6,fig7,fig8,fig9,fig10>

而实际上我们可以不需要开辟栈空间来模拟放置元素，我们只需要用两个指针来进行标记栈顶位置和现在需要放置的元素位置即可。我们用 top 来标记栈顶位置，用 i 来标记现在需要放置的元素位置，那么我们找到原数组中对应放置在最后位置的元素位置，然后在数组最后从该位置元素往前来进行模拟放置即可。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        n = len(arr)
        top = 0
        i = -1
        while top < n:
            i += 1
            top += 1 if arr[i] else 2
        j = n - 1
        if top == n + 1:
            arr[j] = 0
            j -= 1
            i -= 1
        while j >= 0:
            arr[j] = arr[i]
            j -= 1
            if arr[i] == 0:
                arr[j] = arr[i]
                j -= 1
            i -= 1
[sol1-C++]
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
28
29
30
31
class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int n = arr.size();
        int top = 0;
        int i = -1;
        while (top < n) {
            i++;
            if (arr[i] != 0) {
                top++;
            } else {
                top += 2;
            }
        }
        int j = n - 1;
        if (top == n + 1) {
            arr[j] = 0;
            j--;
            i--;
        } 
        while (j >= 0) {
            arr[j] = arr[i];
            j--;
            if (!arr[i]) {
                arr[j] = arr[i];
                j--;
            } 
            i--;
        }
    }
};
[sol1-Java]
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
28
29
30
class Solution {
    public void duplicateZeros(int[] arr) {
        int n = arr.length;
        int top = 0;
        int i = -1;
        while (top < n) {
            i++;
            if (arr[i] != 0) {
                top++;
            } else {
                top += 2;
            }
        }
        int j = n - 1;
        if (top == n + 1) {
            arr[j] = 0;
            j--;
            i--;
        } 
        while (j >= 0) {
            arr[j] = arr[i];
            j--;
            if (arr[i] == 0) {
                arr[j] = arr[i];
                j--;
            } 
            i--;
        }
    }
}
[sol1-C#]
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
28
29
30
public class Solution {
    public void DuplicateZeros(int[] arr) {
        int n = arr.Length;
        int top = 0;
        int i = -1;
        while (top < n) {
            i++;
            if (arr[i] != 0) {
                top++;
            } else {
                top += 2;
            }
        }
        int j = n - 1;
        if (top == n + 1) {
            arr[j] = 0;
            j--;
            i--;
        } 
        while (j >= 0) {
            arr[j] = arr[i];
            j--;
            if (arr[i] == 0) {
                arr[j] = arr[i];
                j--;
            } 
            i--;
        }
    }
}
[sol1-C]
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
void duplicateZeros(int* arr, int arrSize){
    int top = 0;
    int i = -1;
    while (top < arrSize) {
        i++;
        if (arr[i] != 0) {
            top++;
        } else {
            top += 2;
        }
    }
    int j = arrSize - 1;
    if (top == arrSize + 1) {
        arr[j] = 0;
        j--;
        i--;
    } 
    while (j >= 0) {
        arr[j] = arr[i];
        j--;
        if (!arr[i]) {
            arr[j] = arr[i];
            j--;
        } 
        i--;
    }
}
[sol1-JavaScript]
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
28
var duplicateZeros = function(arr) {
    const n = arr.length;
    let top = 0;
    let i = -1;
    while (top < n) {
        i++;
        if (arr[i] !== 0) {
            top++;
        } else {
            top += 2;
        }
    }
    let j = n - 1;
    if (top === n + 1) {
        arr[j] = 0;
        j--;
        i--;
    } 
    while (j >= 0) {
        arr[j] = arr[i];
        j--;
        if (arr[i] === 0) {
            arr[j] = arr[i];
            j--;
        } 
        i--;
    }
};
[sol1-Golang]
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
28
func duplicateZeros(arr []int) {
    n := len(arr)
    top := 0
    i := -1
    for top < n {
        i++
        if arr[i] != 0 {
            top++
        } else {
            top += 2
        }
    }
    j := n - 1
    if top == n+1 {
        arr[j] = 0
        j--
        i--
    }
    for j >= 0 {
        arr[j] = arr[i]
        j--
        if arr[i] == 0 {
            arr[j] = arr[i]
            j--
        }
        i--
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为数组 arr 的长度。需要遍历两遍数组。

  • 空间复杂度：O(1)，仅使用常量空间。

 Comments
On this page
1089-复写零