Блог пользователя ShowStopper728

Removing Elements
Автор ShowStopper728, история, 7 лет назад, По-английски

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 ?

  • Проголосовать: нравится
  • -7
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 .

    → Ответить
»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить