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. 如何name使用 id1或平均小于 O(nid2 ) ？
  2. 如何以平均 O(n) 或更快的顺序name打印所有s ？ id2

我想到了使用排序的哈希表id1和组织的二叉搜索树id2。作为数据结构的初学者，我仍然不确定这种方法。

  1. 就易于实现和使用的数据结构而言，这是最简单的解决方案吗？
  2. 使用两个都基于同一个对象的数据结构会带来任何问题吗？我想知道像我在这里这样的“复制”数据是否会给删除和插入带来任何问题，但也欢迎其他问题和原始问题的解决方案。
4

1 回答 1

2

我确实会使用 aHashMap<Integer, Person>按 ID1 存储人员，并使用 aTreeMap<Integer, Person>按 ID2 存储人员，按 ID2 排序。

第一个是 O(1)，通过 ID1 获取名称。第二个是 O(N) 用于遍历所有值。

要回答您的问题：

  1. 我认为这确实是最简单的解决方案
  2. 确保将两个映射封装在一个提供所需方法的对象中，并同时在两个映射中插入/删除。不要将两张地图暴露在外面。如果您将第二个映射的迭代器或值的集合暴露给外部，请确保Collections.unmodifiableCollection()在返回之前将其包装使用，以防止从外部修改集合。
于 2012-12-08T22:48:04.317 回答