复写零
难度:
标签:
题目描述
代码结果
运行时间: 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`,这个判断的目的是什么?是否可以通过调整i和j的初始位置来避免这种边界检查?
▷