CODEWITHSUNDEEP
javaarraysalgorithm
Scholle
Scholle

Reputation: 1521

How to efficiently implement array element lookup and removal in Java?

Given a sorted array of objects, while the order is based on some object attribute. (Sorting is done via a List using Collections.sort() with a custom Comparator and then calling toArray()).

Duplicate instances of SomeObject are not allowed ("duplicates" in this regard depends on multiple attribute value in SomeObject), but it's possible that multiple instances of SomeObject have the same value for attribute1, which is used for sorting.

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

How to efficiently check whether a certain object based on some attribute is in that array while also being able to "mark" objects already found in some previous look up (e.g. simply by removing them from the array; already found objects don't need to be accessed at later time).

Without the later requirement, one could do a Arrays.binarySearch() with custom Comparator. But obviously it's not working when one want to remove objects already found.

Upvotes: 2

Views: 164

Answers (3)

Eric Kim
Eric Kim

Reputation: 41

If you want you can put all the elements into some sort of linked list whose nodes are also connected in a heap form when you sort them. That way, finding an element would be log n and you can still delete the nodes in place.

Upvotes: 0

Vivin Paliath
Vivin Paliath

Reputation: 95578

Building on Arian's answer, you can also use TreeBag from Apache Commons' Collections library. This is backed by a TreeMap, and maintains a count for repeated elements.

Upvotes: 0

Cephalopod
Cephalopod

Reputation: 15145

Use a TreeSet (or TreeMultiset).

You can initialize it with your comparator; it sorts itself; look-up and removal are in logarithmic time.

You can also check for existence and remove in one step, because remove returns a boolean.

Upvotes: 5

Related Questions