leetcode
leetcode 1001 ~ 1050
复写零

复写零

难度:

标签:

题目描述

代码结果

运行时间: 22 ms, 内存: 16.3 MB


/*
 * 思路:
 * 使用Java Stream API处理数组是有挑战的,因为我们需要在原数组上就地操作,
 * Java Stream不支持直接的就地修改操作。因此,这里提供一种非就地修改的思路,
 * 使用Stream来构造新的数组,然后将结果复制回原数组。
 */
import java.util.Arrays;
import java.util.stream.IntStream;

public class Solution {
    public void duplicateZeros(int[] arr) {
        int[] result = IntStream.range(0, arr.length)
                                 .flatMap(i -> arr[i] == 0 ? IntStream.of(0, 0) : IntStream.of(arr[i]))
                                 .limit(arr.length)
                                 .toArray();
        System.arraycopy(result, 0, arr, 0, arr.length);
    }
}

解释

方法:

题解采用了一种双指针技术来就地修改数组。首先,数组中的零的数量被计算出来,并利用这个信息计算出如果全部复写零后的数组长度。接着,从数组的末尾开始,使用两个指针i和j进行操作:i指向原始数组的末尾,j指向复写零后的虚拟数组末尾。迭代过程中,如果遇到零,则需要在j指向的位置上复写零,如果有空间则复写两次。如果不是零,则将元素复制到j指向的位置。这个过程一直持续到i遍历完数组的开头。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
如何确保在计算新数组长度时不会因原数组长度限制而覆盖数组外的内存?
题解中,尽管计算了新数组的长度(原数组长度加上零的数量),实际操作并不会创建一个真正的新数组,而是利用原数组进行模拟。这种方法通过设置一个虚拟的末尾指针j来模拟新数组,同时确保所有实际的写入操作都不会超出原数组的边界(通过`if j < length`判断)。这种方式确保了不会因数组长度限制而覆盖或访问数组外的内存。
🦆
在计算完零的数量之后,为何需要计算虚拟数组的长度,而不直接在原数组上进行修改?
虚拟数组的长度计算是为了确定在包含复写零后的数组中每个元素的正确位置。如果直接在原数组上进行修改,由于零的复写会导致数组中的元素向后移动,可能会覆盖还未处理的元素,从而导致数据丢失或错误。通过计算虚拟数组长度,并从数组的末尾开始复制和复写零,可以避免这种覆盖,确保每个元素都被正确放置。
🦆
题解中提到的`j指向复写零后的虚拟数组末尾`,这个虚拟数组是如何在计算和操作过程中被定义和使用的?
虚拟数组并不是一个实际存在的数组,而是一个在逻辑上通过计算得出的假设数组,它包含了原数组中的所有元素以及复写的零。虚拟数组的长度由原数组的长度加上原数组中零的数量决定。在实际操作中,我们通过移动指针j来模拟这个虚拟数组的索引,从而确定每个元素(包括复写的零)在原数组中应该放置的位置。
🦆
代码中有两处判断`if j < length`,这个判断的目的是什么?是否可以通过调整i和j的初始位置来避免这种边界检查?
这个判断用于确保不会在原数组的长度外进行写操作,即不会覆盖数组外的内存。由于j的值可能会超出原数组的实际长度(在虚拟数组中),这个判断确保只有当j仍在原数组的有效范围内时才进行元素的复写或复制。通过调整i和j的初始位置可以减少边界检查的次数,但完全避免这种检查并不可行,因为我们需要确保每次写入都在安全的数组范围内。

相关问题