这里有几点需要注意。

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

注意，这个操作是O（size）。但是由于它发生在容量为1，2，4，8，16，32...的情况下，所以 * 总运行时间 * 也是O（size）。这被称为 * 摊销复杂度O（1）*。形式上，对于每k个操作，前k个操作在O（k）时间内完成。有些操作是昂贵的，但是它们足够罕见。
有很多方法可以让一个可扩展的数组的每个操作的代价真实的（1），而不是摊销，代价是更大的常数因子。其中一种方法是提前创建下一个数组，同时维护数组的两个副本，并且每增加一个，就把两个元素复制到下一个数组中。如果这是焦点，那么它值得一个单独的问题。

**其次，**在扩展了底层容器之后，**无论如何，将元素插入二进制堆都可以高效地在O（log n）内完成。只需将元素作为最后一个元素添加，然后筛选它直到它停止。因此，如果我们满足 * 每个操作的摊销时间为O（log n）*，我们可以使用上面的扩展策略和自然的堆插入操作，唯一的问题是如果我们想要的是真实的O（logn），而不是摊销的，但在问题中应明确提及。
**第三，**如果你坚持在容器扩展时对元素进行重新排序，那么它的开销和容器扩展的开销是一样的。记住，在每次扩展时，我们都必须将旧的内容复制到新的数组中，这需要O（size）的时间。现在，我们可以只复制到我们选择的位置，而不是相同的位置。在你的例子中，我们选择[0]->[1]。[1，2]->[3，4]、[3，4，5，6]->[7，8，9，10]，依此类推。

如果真的需要，就像摊销的O（1）被转换成每个元素加法的实数O（1）一样，我们可以提前创建下一个数组，并在每次加法时复制两个以上的元素。尽管我们必须维护两个副本，所以堆操作也会有更大常数因子的O（log 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]

型