ShowStopper728's blog

Removing Elements
By ShowStopper728, history, 7 years ago, In English

I need to know a way to remove elements in O(1) time . I used hash table , put the values as keys but there is a problem that the values are not distinct . Is there a way to remove elements in O(1) time if they aren't distinct ?

  • Vote: I like it
  • -7
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm not exactly sure of what you mean, but using a linked list seems to be the solution to your problem.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No , I don't think that it will work . What I meant is that assume you have an array of numbers . You perform some operations and then come up with a number , you want to delete this element from the array in O(1) time . I want to know what is the best data structure to use at this moment .

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You could use a hash table of vectors where each entry of the hash table consist of the list of indexes of that value that you want to delete. If you want to select a particular index in O(1) time, you can compress the indexes.

→ Reply