如何在Java中有效地实现数组元素查找和删除？

Question

给定排序的对象数组,而顺序基于某些对象属性.(使用Collections.sort()通过List与自定义Comparator进行排序,然后调用toArray()).

不允许SomeObject的重复实例(在这方面"重复"取决于SomeObject中的多个属性值),但SomeObject的多个实例可能具有相同的attribute1值,用于排序.

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]);

如何有效地检查基于某个属性的某个对象是否在该数组中,同时还能够"标记"在先前查找中已经找到的对象(例如,只需从数组中删除它们;已经找到的对象不需要稍后访问).

如果没有后面的要求,可以使用自定义Comparator执行Arrays.binarySearch().但显然当想要删除已找到的对象时,它不起作用.

Answer 1

使用TreeSet(或TreeMultiset).

你可以用你的比较器初始化它; 它自我排序; 查找和删除是对数时间.

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