Алгоритм для перевода списка операций на индекс - PullRequest
Новая
       16

Алгоритм для перевода списка операций на индекс

0 голосов
/ 10 июня 2019

Предположим, у вас есть несортированный список различных предметов.например: 

['a', 'z', 'g', 'i', 'w', 'p', 't']

Вы также получите список операций вставки и удаления.Операции вставки состоят из индекса для вставки и элемента для вставки.Например: Insert (5, 's')

Операции удаления выражаются с использованием элемента для удаления.Например: Удалить ('s')

Таким образом, список операций может выглядеть следующим образом:

  • Вставить ('s', 5)
  • Удалить ('p')
  • Вставить ('j', 0)
  • Удалить ('a')

Я ищу наиболее эффективный алгоритм, который можно перевестисписок операций, так что они основаны на индексе.Это означает, что нет необходимости изменять операции вставки, но операции удаления должны быть заменены операцией удаления с указанием индекса current удаляемого элемента (не исходного).

Таким образом, выходные данные примера должны выглядеть следующим образом:

  • Начальный набор: ['a', 'z', 'g', 'i', 'w', 'p', 't']
  • Вставка ('s', 5) (список теперь: ['a', 'z', 'g', 'i', 'w', 's', 'p ',' t ']
  • Удалить (6) (список теперь: [' a ',' z ',' g ',' i ',' w ',' s ',' t ']
  • Вставить ('j', 0) (список теперь: ['j', 'a', 'z', 'g', 'i', 'w', 's', 't ']
  • Удалить (1) (список теперь: [' j ',' z ',' g ',' i ',' w ',' s ',' t ']

Очевидно, что мы можем сканировать следующий элемент для удаления в наборе после каждой операции, и это будет означать, что весь алгоритм будет принимать O (n * m), где n - размер списка, а mтакое количество операций.

Вопрос - есть ли более эффективный алгоритм?

1 Ответ

0 голосов
/ 10 июня 2019

Вы можете сделать это более эффективным , если у вас есть доступ ко всем операциям remove раньше времени, и они значительно (определены в контексте) короче, чем объект список.

Вы можете вести список предметов, представляющих интерес: те, которые будут удалены. Посмотрите их начальные позиции - либо в исходном списке, либо после вставки. Всякий раз, когда вставка выполняется в позиции n, каждый элемент этого списка после этой позиции увеличивает свой индекс на единицу; для каждого такого удаления уменьшите на единицу.

Это мало отличается от уже очевидных методов; это просто количественно быстрее, потенциально меньше m по сложности O (n * m) .

...