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. ..。

このアルゴリズムには1つずつバグがあることに注意してください。比較的簡単に修正できるはずです。

更新：あなたの問題がはるかに単純であることに気づきました。あなたの場合は、イテレータを作成し、X時間を進めて、そのイテレータを使用して要素を1つずつ追加します。

于 2012-07-22T14:36:08.847 に答える
2

java.util.LinkedListを使用していると仮定すると、 ListIterator を返すLinkedList.listIterator () メソッドがあります。

public ListIterator listIterator(int インデックス)

リスト内の指定された位置から始まる、このリスト内の要素のリスト反復子を (適切な順序で) 返します。[...]

リスト反復子はフェイルファストです。リスト反復子が作成された後、リスト反復子自体の削除または追加メソッド以外の方法でリストが構造的に変更された場合、リスト反復子は ConcurrentModificationException をスローします。[...]

また、 ListIterator.add () を使用して、LinkedList の途中にアイテムを安全に追加できます。

void add(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 に答える