Easy

题目描述

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

示例 2：

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

提示：

  • 1 <= arr.length <= 10^4
  • 0 <= arr[i] <= 9

解题思路

这道题要求在原数组上就地修改，将每个零复写一遍。核心挑战是避免覆盖还未处理的元素。

方法一：辅助数组（简单直观）

  • 创建临时数组，遍历原数组，遇到零就写入两个零，遇到非零就写入原值
  • 将临时数组的内容复制回原数组
  • 时间复杂度O(n)，空间复杂度O(n)

方法二：双指针法（推荐） 这是最优解法，真正实现就地修改：

  1. 第一次遍历：统计零的个数，计算扩展后的长度
  2. 第二次遍历：从后往前处理，避免覆盖未处理的元素
    • 使用两个指针：i指向原数组末尾，writeIdx指向扩展后的写入位置
    • 如果当前元素是零，写入两个零；否则写入原值
    • 从右往左处理确保不会覆盖还需要处理的元素

关键思路：通过计算扩展长度，确定每个元素的最终位置，然后反向填充，巧妙避免了元素覆盖问题。

代码实现

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int n = arr.size();
        int zeroCount = 0;
        
        // 统计零的个数
        for (int num : arr) {
            if (num == 0) zeroCount++;
        }
        
        // 从后往前处理
        int i = n - 1;
        int writeIdx = n + zeroCount - 1;
        
        while (i >= 0) {
            if (arr[i] != 0) {
                // 非零元素
                if (writeIdx < n) {
                    arr[writeIdx] = arr[i];
                }
            } else {
                // 零元素，需要写入两个零
                if (writeIdx < n) {
                    arr[writeIdx] = 0;
                }
                writeIdx--;
                if (writeIdx < n) {
                    arr[writeIdx] = 0;
                }
            }
            i--;
            writeIdx--;
        }
    }
};

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        n = len(arr)
        zero_count = arr.count(0)
        
        # 从后往前处理
        i = n - 1
        write_idx = n + zero_count - 1
        
        while i >= 0:
            if arr[i] != 0:
                # 非零元素
                if write_idx < n:
                    arr[write_idx] = arr[i]
            else:
                # 零元素，需要写入两个零
                if write_idx < n:
                    arr[write_idx] = 0
                write_idx -= 1
                if write_idx < n:
                    arr[write_idx] = 0
            
            i -= 1
            write_idx -= 1

public class Solution {
    public void DuplicateZeros(int[] arr) {
        int n = arr.Length;
        int zeroCount = 0;
        
        // 统计零的个数
        foreach (int num in arr) {
            if (num == 0) zeroCount++;
        }
        
        // 从后往前处理
        int i = n - 1;
        int writeIdx = n + zeroCount - 1;
        
        while (i >= 0) {
            if (arr[i] != 0) {
                // 非零元素
                if (writeIdx < n) {
                    arr[writeIdx] = arr[i];
                }
            } else {
                // 零元素，需要写入两个零
                if (writeIdx < n) {
                    arr[writeIdx] = 0;
                }
                writeIdx--;
                if (writeIdx < n) {
                    arr[writeIdx] = 0;
                }
            }
            i--;
            writeIdx--;
        }
    }
}

var duplicateZeros = function(arr) {
    let zeros = 0;
    let n = arr.length;
    
    for (let i = 0; i < n - zeros; i++) {
        if (arr[i] === 0) {
            if (i === n - zeros - 1) {
                arr[n - 1] = 0;
                n--;
                break;
            }
            zeros++;
        }
    }
    
    let last = n - zeros - 1;
    for (let i = n - 1; i >= 0; i--) {
        if (arr[last] !== 0) {
            arr[i] = arr[last];
        } else {
            arr[i] = 0;
            i--;
            arr[i] = 0;
        }
        last--;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型双指针法（推荐）辅助数组法
时间复杂度O(n)O(n)
空间复杂度O(1)O(n)

说明：

  • 双指针法是最优解，实现了真正的就地修改
  • 辅助数组法虽然思路简单，但需要额外空间
  • 两种方法时间复杂度相同，但空间复杂度差异明显