复写零

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

输入arr

对数组arr的0元素复写到下一个位置且其余元素依次后移一位超过数组长度的元素会被丢弃。

(2)

O(1)的要求额外创建一个长度为假设数组arr长度为nn的数组nums遍历arr数组如果当前元素等于0就2次写入nusm否则当前元素1次写入nums;直到新数组nums被写满就停止此时nums中就保存着复写的结果。

(2)

使用快慢双指针算法定义快指针dest指向复写后的位置慢指针cur指向复写前的位置

(3)

如果直接从前往后进行复写操作明显是行不通的因为arr[cur]0时dest走两步而cur一直走一步会出现cur未遍历到的元素被覆盖的情况

(4)

首先明确一点dest一定不慢于cur故初始的前后位置情况一定是dest与cur相等或dest在cur之后。

完全模拟正着复写0操作直到cur遍历完整个数组arr此时dest大概率是处于越界位置的。

只模拟到有效位置

如果nums[cur]0则nums[dest]和nums[dest-1]位置均被设置为0之后dest-2

反之nums[cur]!0则nums[dest]位置被设置为nums[cur]的值之后dest--

时间复杂度

第一步模拟复写0时遍历了一遍数组第三步从cur位置往前复写时也遍历了一遍数组故时间复杂度是

O(n)

此时dest模拟复写dest2后为destn之后循环结束。

/*

特殊处理这种情况此时是复写0但只有前1个0有效后一个0越界了。

为使下文正常复写调整复写位置真正复写时从最后复写位置的前一个位置开始让dest-2cur--并直接对最后复写位置特殊复写*/if(dest

n){dest