mercredi 26 février 2020

A standard java class for removing a random element

I would like to find a class that supports the following interface efficiently:

  • Add element
  • Remove element, given its key
  • Remove a random element

By "efficiently", I mean O(1) or constant time.

One way to achieve this is to have a class that contains an array and a hashmap.

  • Add element: Add it to both, and keep in the element its location in the array
  • Remove element by key: Remove from the hashmap and use the saved location to remove it from the array
  • Remove a random element: Choose a random cell in the array and remove the element in that cell. use the key to remove it from the hash.

Whenever we remove an element from the array, simply replace it by the last element and update the array size.

I could write this kind of a class, but I wonder whether such a class is already available.




Aucun commentaire:

Enregistrer un commentaire