本文主要是介绍力扣1089题 复写零 双指针解法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
2. 复写零
给你一个长度固定的整数数组
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]
算法思路
本题使用双指针算法.
如果[从前往后]进行原地复写的话, 由于0
会复写两次, 导致没有被复写的数被[覆盖]掉了. 因此我们使用[从后向前]的复写策略.
算法流程
-
初始化两个指针
cur = 0
,dest = -1
-
先找到最后一个复写的数, 使
cur
指向最后一个复写的数,dest
指向从后往前复写的起始位置, 应该是数组的最后一个元素的位置.-
当
cur < arr.length
时, 一直执行下面的循环:-
先判断
cur
位置的值- 如果为
0
,dest
向后移动2步 - 如果不是
0
,dest
向后移动1步
- 如果为
-
判断
dest
是否已经到达数组的最后一个元素的位置, 如果到达了, 就终止循环. -
cur++
, 继续判断
-
-
-
处理边界情况. 判断
dest
是否发生越界(dest = arr.length
):如果发生了越界:
- 让数组
arr[arr.length - 1] = 0
cur--
dest -= 2
- 让数组
-
"从后向前"完成复写操作, 只要
cur >= 0
- 判断
cur
位置的值- 如果是
0
:dest
和dest - 1
位置的值改为0
,dest -= 2
- 如果不是
0
:dest
位置的值改为cur
位置的值,dest--
- 如果是
cur--
- 判断
Java代码
class Solution {public static void duplicateZeros(int[] arr) {int cur = 0, dest = -1;while (cur < arr.length) {if(arr[cur] == 0) {dest += 2;} else {dest++;}if(dest >= arr.length - 1) {break;}cur++;}if(dest >= arr.length) {arr[arr.length - 1] = 0;dest -= 2;cur--;}while (cur >= 0) {if(arr[cur] == 0) {arr[dest--] = 0;arr[dest--] = 0;cur--;} else {arr[dest--] = arr[cur--];}}}
}
时间复杂度: O(N) 空间复杂度O(1)
这篇关于力扣1089题 复写零 双指针解法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!