前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode 1089. 复写零

Leetcode 1089. 复写零

作者头像
zhipingChen
发布2020-02-13 13:02:12
4150
发布2020-02-13 13:02:12
举报
文章被收录于专栏:编程理解

题目描述

给你一个长度固定的整数数组 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]

解法

由描述可知,该题目要求在数组中的每个零后添加一个零,原零后数组元素右移一位。

最简单方式自然是遍历数组元素,每遇到一个零,将后续所有元素右移一位,填入零元素,直至数组末尾。但是该方式下,一个元素可能存在多次重复移动的操作,如果能直接确定每一个元素的最终位置,一次将元素移动到最终位置的话,则执行上较为高效。

由题目可知,每个元素的最终位置为,当前元素位置加上该元素前零的个数。所以不妨计算出元素前零的个数,则可以直接一次将元素移动到最终位置上。

在遍历数组计算零的个数时,不一定遍历到数组末尾,因为数组中若存在零,则必然有元素被移除数组; 需要注意下,如果最后一个元素是零的话,需要判断复写该零值,是否超出数组边界。

代码语言:javascript
复制
class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        count,i=0,0
        while i+count<len(arr):
            if arr[i]==0:
                count+=1
            i+=1
        i-=1
        if i+count==len(arr):
            arr[-1],count,i=0,count-1,i-1
        while i>=0 and count>0:
            arr[i+count]=arr[i]
            if arr[i]==0:
                count-=1
                arr[i+count]=0
            i-=1
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档