能用的网站,济南网站建设专业,免费seo排名网站,昆明做网站优化哪家好2. 复写零 给你一个长度固定的整数数组 arr #xff0c;请你将该数组中出现的每个零都复写一遍#xff0c;并将其余的元素向右平移。 注意#xff1a;请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改#xff0c;不要从函数返回任何东西。 示例 1请你将该数组中出现的每个零都复写一遍并将其余的元素向右平移。 注意请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改不要从函数返回任何东西。 示例 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] 0cur--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)
