有没有办法以系统的方式将数组中的小块元素复制并移动到 Java 中新增长的数组中的左侧(log(n))?

is there a way to copy and shift small blocks of elements in an array to the left in a new grown array in java in o(log(n)) in a systematic way?

提问人:WastedxBusted 提问时间:11/15/2023 更新时间:11/15/2023 访问量:76

问:

假设我们有一个数组,它充当隐式二进制堆,我们从:

[0, 0, 0]

它慢慢地被填满:

[3, 2, 3]

我们需要通过将其复制到大小为 2n + 1 的新增长数组中来扩展它,其中 n 是旧数组的长度,但这次我们将一些元素块复制到增长数组中的某些位置,例如:

[0, 3, 0, 2, 3, 0, 0]

假设上面的数组被填满了,我们需要再次增长,它看起来像这样:

[5, 3, 5, 2, 3, 4, 5]

    |
    |
   \|/

[0, 5, 0, 3, 5, 0, 0, 2, 3, 4, 5, 0, 0, 0, 0]

我希望你现在明白了转变的模式。

那么有没有办法使用 System.arraycopy() 在 o(log(n)) 中实现这种转换模式的方式?如果没有,您能否建议任何其他替代方案。

Java 数组 算法

评论

2赞 trincot 11/15/2023
不,这不能在 o(log(n)) 时间内完成,因为所有 n 个项目都需要移动,所以它将是 O(n)。但退后一步,你为什么要长出这样的一堆?首先,它变成了一个无效的堆,因为违反了堆不变性。
0赞 Neil 11/15/2023
这不是隐式二进制堆的标准。您没有分配连续块的原因是什么?
2赞 trincot 11/15/2023
这就是在二进制堆中筛选的原则。根将具有最大值。但是,通过添加零,您将破坏此属性。我看不出这有什么用。
1赞 user85421 11/15/2023
像这样的东西?(不知道它是什么,来不及考虑它)for (int i=0,j=1,k=1; i<len; i+=k,j+=2*k,k*=2) arraycopy(src, i, dst, j, min(k, len-i));O()
1赞 Neil 11/15/2023
我需要更多关于这样做动机的背景信息来理解你的算法。就目前而言,我不确定这有什么用。

答:

-1赞 Reilas 11/15/2023 #1

"...我们需要通过将其复制到大小为 2n + 1 的新增长数组来扩展它,其中 n 是旧数组的长度,但这次我们将一些元素块复制到增长数组中的某些位置......”

下面是一个没有 arraycopy 的示例。

int[] increase(int[] a) {
    int[] na = new int[(a.length * 2) + 1];
    for (int i = 1, j = 0, n = na.length; i < n; i += 2, j++)
        na[i] = a[j];
    return na;
}

输出

a = [3, 2, 3]
na = [0, 3, 0, 2, 0, 3, 0]

评论

0赞 trincot 11/15/2023
但那不是 O(log(n))
1赞 WastedxBusted 11/15/2023
所需的移位模式不是那个,我希望数组 na 是 [0, 3, 0, 2, 3, 0, 0]
0赞 Reilas 11/15/2023
@WastedxBusted,调整它。
0赞 WastedxBusted 11/15/2023
@Reilas这不是要调整它,逻辑还差得很远,但我会尝试稍微调整一下逻辑。
1赞 Gassa 11/15/2023 #2

这里有几点需要注意。


首先,观察通常的策略,即拥有一个可以有效地向右扩展的数组。 一个例子是 C++。 稍微简化一点,数组具有显式大小和隐式容量。 分配的内存与容量匹配。 使用的内存与大小匹配。 当我们扩展数组并且大小小于容量时,我们开始使用下一个分配的元素 O(1) 成本。 当大小等于容量时,我们创建一个两倍大的副本,将内容移动到那里,然后开始使用新副本。std::vector

请注意,此操作为 O(size)。 但是由于它发生在容量 1、2、4、8、16、32...,因此总运行时间也是 O(大小)。 这称为摊销复杂度 O(1)。 从形式上讲,对于每 k 个操作,前 k 个操作都在 O(k) 时间内完成。 有些手术很昂贵,但很少见。

有一些方法可以创建一个可扩展的数组,其中每个操作的成本是实际的 O(1),而不是摊销,代价是更大的常数因子。 其中一种方法是提前创建下一个数组,同时维护数组的两个副本,并且每增加一个副本,就将另外两个元素复制到下一个数组中。 如果这是重点,那么它值得一个单独的问题。


其次,在扩展底层容器后,无论如何都可以在 O(log n) 中有效地将元素插入二进制堆中。 只需将元素添加为最后一个元素,然后对其进行筛选,直到它停止。 因此,如果我们对每个操作的摊销 O(log n) 感到满意,我们可以只使用上述策略进行扩展和自然堆插入操作。唯一的问题是,如果我们想要真正的 O(log n),而不是摊销,那么它就值得在问题中明确提及。


第三,如果坚持在容器扩容时对元素进行重新排序,其成本与容器扩容成本相同。 请记住,在每次扩展时,我们必须将旧内容复制到新数组中,这需要 O(size) 时间。 好吧,此时此刻,我们可以复制到我们选择的地方,而不是相同的地方。 在您的示例中,我们选择 [0]->[1]、[1,2]->[3,4]、[3,4,5,6]->[7,8,9,10],依此类推。

如果真的需要,就像摊销的 O(1) 被转换为每个元素添加的实际 O(1) 一样,我们可以提前创建下一个数组,并在每次添加时再复制两个元素。 但是,我们必须维护这两个副本,因此,堆操作的 O(log n) 也将具有更大的常数因子。