java - Java中如何高效地实现数组元素查找和删除？

Question

给定一个排序的对象数组，而顺序基于某个对象属性。（排序是通过使用 Collections.sort() 和自定义比较器然后调用 toArray() 的列表完成的）。

不允许 SomeObject 的重复实例（“重复”在这方面取决于 SomeObject 中的多个属性值），但 SomeObject 的多个实例可能具有相同的属性 1 值，用于排序。

public SomeObject {
  public attribute1;
  public attribute2;
}

List<SomeObject> list = ...
Collections.sort(list, new Comparator<SomeObject>() {
  @Override
  public int compare(SomeObject v1, SomeObject v2) {
    if (v1.attribute1 > v2.attribute1) {
      return 1;
    } else if (v1.attribute1 < v2.attribute1) {
      return -1;
    } else
      return 0;
  }
});
SomeObject[] array = list.toArray(new SomeObject[0]);

如何有效地检查基于某个属性的某个对象是否在该数组中，同时还能够“标记”在以前的查找中已经找到的对象（例如，只需从数组中删除它们；已经找到的对象不需要稍后访问）。

如果没有后面的要求，可以使用自定义比较器执行 Arrays.binarySearch()。但显然，当一个人想要删除已经找到的对象时，它是行不通的。

Answer 1

使用TreeSet（或TreeMultiset）。

您可以使用比较器对其进行初始化；它自己排序；查找和删除是在对数时间内进行的。

您还可以一步检查是否存在并删除，因为remove返回一个布尔值。

Answer 2

如果您愿意，您可以将所有元素放入某种链表中，当您对它们进行排序时，其节点也以堆形式连接。这样，找到一个元素将是 log n 并且您仍然可以删除适当的节点。

Answer 3

基于 Arian 的回答，您还可以TreeBag从 Apache Commons 的 Collections 库中使用。这由 a 支持TreeMap，并维护重复元素的计数。