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