算法随笔_36: 复写零

上一篇:算法随笔_35: 每日温度-CSDN博客

=====

题目描述如下:

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

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

示例 1：

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

=====

算法思路:

这道题如果没有后边的条件(需要原地修改数组) ，比较容易解决。我们可以新开辟一段同样长度的数组res，然后定义两个指针p1,  p2，p1指向原数组首元素，p2指向res数组首元素。然后从右往左枚举原数组arr。如果访问到的arr[p1]不为0，那么把arr[p1]赋值给res[j]，然后j向右移动一格。如果访问到的arr[p1]为0，那么连续j向右移动两格，每个格都赋值为0。以此类推，直到p2到达数组res末尾。

但如果需要原地修改数组，就需要多想想，再仔细分析一下这道题。

我们发现，还用上面的方法，直接在原数组修改，当遇到0的时候，p2指针会覆盖两个格子的元素。碰到越多0，覆盖的原值就越多。由于p2指针走的快，导致，当p1访问的时候，一些原值已经不复存在。这个问题如何解决呢？

我们发现，由于p2比p1走的快，当p2到达数组末尾时，p1还未到达末尾。也就是说p1到p2这段的元素是不需要p1访问的，最终的结果数组，也用不到这些元素。所以我们可以考虑从右往左修改数组。具体的操作如下:

1.  设结尾索引end_ind。我们从左往右枚举数组arr，索引值存于变量i。碰到值为非0的元素，end_ind加1。碰到值为0的元素，end_ind加2。直到end_ind大于等于数组长度退出。此时变量i就是需要保留的所有元素的最大索引。

2.  设变量j为数组的最后一个索引。

3. 我们从索引i处，从右往左枚举数组arr。如果arr[i]不为0，我们把arr[i]赋值给arr[j]，然后j左移一格。如果arr[i]为0，我们把j连续向左移动两格，每个格都赋值为0。同时i也左移一格。当i小于0时，退出枚举，程序完成。

这里有个细节，需要补充一下，有可能end_ind大于数组长度。比如arr=[1,0]，end_ind=3。由于长度肯定不能超过原数组长度。因此，在步骤2的时候，我们需要先判断一下，如果end_ind大于数组长度，需要把最后一个元素设为0。i，j各自减1，然后再运行步骤3。

此算法时间复杂度为O(n) 。下面是代码实现:

class Solution:
    def duplicateZeros(self, arr):
        arr_len= len(arr)
        end_ind=0
        i=0
        while i < arr_len:
            num=arr[i]
            if num==0:
                end_ind+=2
            else:
                end_ind+=1
            if end_ind>=arr_len:
                break
            i+=1
            
        j=arr_len-1
        if end_ind>arr_len:
            arr[j]=0
            j-=1
            i-=1
        while i >=0:
            arr[j]=arr[i]
            j-=1
            if arr[i]==0:
                arr[j]=0
                j-=1
            i-=1