4

次のように実装された多くのノードがあります。

public class Person{
    private String name;
    private int id1;
    private int id2;
    private Node next; // or left/right, depending on what you're using.
}
  1. または平均で O(n) 未満nameを使用 するにはどうすればよいですか?id1id2
  2. nameすべての sを平均 O(n) 以上の順序で 印刷する方法は?id2

で順序付けされたハッシュ テーブルと でid1編成された二分探索木を使用することを考えましたid2。データ構造の初心者として、私はまだこのアプローチについて確信が持てません。

  1. 実装の容易さと使用されるデータ構造の点で、これは最も単純なソリューションですか?
  2. どちらも同じオブジェクトに基づく 2 つのデータ構造を使用すると、問題が発生しますか? ここにいるようにデータを「複製」すると、削除と挿入に問題が生じるかどうか疑問に思っていますが、元の質問に対する他の問題と解決策も大歓迎です。
4

1 に答える 1

2

HashMap<Integer, Person>ID1 で人を格納するには a を使用し、TreeMap<Integer, Person>ID2 で並べ替えて ID2 で人を格納するには a を使用します。

最初のものは ID1 で名前を取得するための O(1) です。2 つ目は、すべての値を反復処理するための O(N) です。

質問に答えるには:

  1. これが確かに最も簡単な解決策だと思います
  2. 必要なメソッドを提供し、両方のマップを一度に挿入/削除するオブジェクトに 2 つのマップをカプセル化してください。2 つのマップを外部に公開しないでください。Collections.unmodifiableCollection()2 番目のマップのイテレータまたは値のコレクションを外部に公開する場合は、返す前に必ず使用してラップし、外部からのセットの変更を防ぎます。
于 2012-12-08T22:48:04.317 に答える