likes
comments
collection
share

1089. 复写零 : 双指针运用题

作者站长头像
站长
· 阅读数 18

题目描述

这是 LeetCode 上的 1089. 复写零 ,难度为 简单

Tag : 「双指针」

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

注意:请不要在超过该数组长度的位置写入元素。

要求:请对输入的数组 就地 进行上述修改,不要从函数返回任何东西。

示例 1:

输入:[1,0,2,3,0,4,5,0]

输出:null

解释:调用函数后,输入的数组将被修改为:[1,0,0,2,3,0,0,4]

示例 2:

输入:[1,2,3]

输出:null

解释:调用函数后,输入的数组将被修改为:[1,2,3]

提示:

  • 1<=arr.length<=100001 <= arr.length <= 100001<=arr.length<=10000
  • 0<=arr[i]<=90 <= arr[i] <= 90<=arr[i]<=9

双指针

这道题挺有意思的,建议大家在看文字的同时,在纸上推导一遍。

我们可以假设已经通过原数组 arr 处理出最终的目标数组 ans,起始使用指针 iii 指向原数组的开头位置,使用指针 jjj 指向目标数组的开头位置。

然后开始同时从前往后处理,默认情况下,两个指针每次往后移动一位,当在原数组中出现 arr[i]=0arr[i] = 0arr[i]=0 时,根据题意,我们需要在目标数组 ans[j]ans[j]ans[j] 后面复写多一位,因此此时让 jjj 多走一位。

jjj 走到的位置已超出数组长度,此时 iii 也停在了该被截断的位置的下一位。

此时我们先将 iiijjj 同时往回走一步,确保 iii 落在真正的截断后的位置,但需要注意,由于 jjj 在之前的往前走逻辑中可能会走两步,因此 jjj 在往回走一步后仍可能在数组以外的位置。

然后考虑如何在 iiijjj 所在位置开始「往回」赋值:每次将 arr[i]arr[i]arr[i] 赋值给 arr[j]arr[j]arr[j](需要确保 jjj 下标合法),由于 iii 必然不会出现在 jjj 的后面(即不会出现 j<ij < ij<i),因此不会出现值被提前覆盖的问题。因此通常情况下,我们可以不断的同时减少 iiijjj,并将 arr[i]arr[i]arr[i] 赋值给 arr[j]arr[j]arr[j]。当出现 arr[i]=0arr[i] = 0arr[i]=0 时,我们需要额外让 jjj 往前多走一步,并将该位置置为 000,来实现目标数组「复写零」的效果。

iii 指针越过开头的位置,说明已完成从 arrans 的转换。

这个往回赋值的过程,十分建议大家在纸上推导一遍。

代码:

class Solution {
    public void duplicateZeros(int[] arr) {
        int n = arr.length, i = 0, j = 0;
        while (j < n) {
            if (arr[i] == 0) j++;
            i++; j++;
        }
        i--; j--;
        while (i >= 0) {
            if (j < n) arr[j] = arr[i];
            if (arr[i] == 0 && --j >= 0) arr[j] = 0;
            i--; j--;
        }
    }
}
  • 时间复杂度:O(n)O(n)O(n)
  • 空间复杂度:O(1)O(1)O(1)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1089 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。