随笔

Leetcode 1089. 复写零

2020-01-12  本文已影响0人  zhipingChen

题目描述

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

解法

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

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

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

在遍历数组计算零的个数时,不一定遍历到数组末尾,因为数组中若存在零,则必然有元素被移除数组;

需要注意下,如果最后一个元素是零的话,需要判断复写该零值,是否超出数组边界。

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
上一篇下一篇

猜你喜欢

热点阅读