2.复写零

平凡之路.

发布于 2025-01-23 08:54:55

1090

文章被收录于专栏：学习学习

LeetCode 1089. 复写零

1. 题目描述

给你一个长度固定的整数数组 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⁴
0 <= arr[i] <= 9

2. 解题思路

在本题中，如果直接采用「从前向后」复写的方式，零的复写会导致后续未处理的元素被覆盖。因此我们选择「从后向前」的复写策略。

核心思路：

复写过程分为两个步骤：
1. 找到复写的边界位置：遍历数组，计算复写到数组末尾时的指针位置。
2. 从后向前复写数组：从最后一个需要复写的元素开始倒序复写，遇到零时写两次，遇到非零元素时写一次。
具体方法：
- 第一步：遍历数组，找到「最后一个需要复写的数字」的索引。
  - 使用两个指针：
    - cur：用于遍历数组。
    - des：记录复写的目标位置。
  - 遍历时更新目标位置，并在到达边界时停止。
- 第二步：从边界位置开始，倒序复写数组，确保未处理的元素不会被覆盖。

边界处理：

如果复写过程中超出了数组的长度，需在边界处特殊处理。

3. 算法代码

以下是 C++ 实现：

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int n = arr.size();
        int cur = 0, des = -1;

        // 1. 找到最后一个需要复写的数
        while (cur < n) {
            if (arr[cur] != 0) {
                des++;
            } else {
                des += 2;
            }
            if (des >= n - 1) break;
            cur++;
        }

        // 2. 边界处理
        if (des == n) {
            arr[n - 1] = 0;
            cur--;
            des -= 2;
        }

        // 3. 从后向前复写
        while (cur >= 0) {
            if (arr[cur] != 0) {
                arr[des--] = arr[cur--];
            } else {
                arr[des--] = 0;
                arr[des--] = 0;
                cur--;
            }
        }
    }
};