2

将元素添加到链表已知是 O(1)。

但是，将其添加到位置 X 是 O(X)，如果我想在该位置添加 R 个元素，则总运行时间将为 O(R*X)。

但必须有一个 O(X+R) 解决方案。

问题是如何在java中做O(R+X)？

4

3 回答 3

2

您有一个配对列表，(element, X)其中X是一个索引，并且element是您要放在该索引下的项目。使用 .对该列表进行排序X并一个接一个地添加元素Iterator。这是一个例子：

您的输入是：[(E1, 5), (E2, 3), (E3, 7)].

  1. 按索引排序：[(E2, 3), (E1, 5), (E3, 7)]

  2. 创建一个迭代器并将其推进3.

  3. E2使用迭代器添加。

  4. 2通过( )推进相同的迭代器5 - 3。

  5. 添加E1.

  6. ...

请注意，此算法有一个错误。修复它应该相对容易。

更新：刚刚注意到您的问题要简单得多。在您的情况下，只需创建一个迭代器，将其推进X时间并使用该迭代器一一添加元素。

于 2012-07-22T14:36:08.847 回答
2

假设您使用的是java.util.LinkedList，有一个返回 ListIterator 的LinkedList.listIterator () 方法：

public ListIterator listIterator(int index)

返回此列表中元素的列表迭代器（以正确的顺序），从列表中的指定位置开始。[...]

列表迭代器是快速失败的：如果列表在创建迭代器后的任何时间进行结构修改，除了通过列表迭代器自己的删除或添加方法之外的任何方式，列表迭代器将抛出 ConcurrentModificationException。[...]

并且可以使用ListIterator.add () 在 LinkedList 的中间安全地添加一项：

无效添加（E e）

将指定元素插入列表（可选操作）。[...]

例如，假设您要将 list2 放在 list1 的第 5 位，您可以通过执行以下操作来实现：

LinkedList list1 = ...;
LinkedList list2 = ...;

ListIterator it1 = list1.listIterator(5);
for (Object item : list2) {
    it1.add(item);
}
于 2012-07-22T14:51:12.937 回答
1

将元素放入集合中，然后您可以使用addAll方法将它们全部添加。

于 2012-07-22T14:36:26.027 回答