Алгоритм расчета новой позиции элементов в списке - PullRequest
Новая
       23

Алгоритм расчета новой позиции элементов в списке

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

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

Например. Предположим, у нас есть следующий список: 

['a', 'x', 'b', 'w', 'e'].

Мы выполняем следующие операции (индексы начинаются с нуля):

  • Вставьте 'u' в 3
  • Удалить в 5
  • Вставьте 'j' в 0
  • Удалить в 1

Новый список: 

['j', 'x', 'b', 'u', 'w']

и я хочу узнать новый индекс элемента, который был с индексом 3 ('w' - ответ 4).

Конечно, я всегда могу пройтись по списку и найти индекс 'w' - что потребовало бы O (N).

Я ищу алгоритм, который даст ответ на вопрос "какова новая позиция элемента, который был в позиции n". Алгоритм может добавлять вычисления O (1) к операциям вставки и удаления. При запросе алгоритм должен возвращать новую позицию элемента менее чем за O (N). (O (log n) возможно, или даже O (1), если это возможно).

Редактировать Просто чтобы быть более конкретным. Алгоритм, который я ищу, запускается после того, как набор изменений сделан. У нас может быть единовременная настройка, которая создает структуру данных, которую позже можно запросить для новой позиции элемента, учитывая его исходную позицию. Предположим, размер списка равен N, количество операций равно M. Также предположим, что K = Max (N, M).

  • Время установки может занять O (k * log K), но предпочтительно использовать O (K).
  • Время одного запроса должно быть меньше O (K) (например, O (log K) или O (1))

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

Ответы [ 2 ]

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

Вот алгоритм для этого: O(log n) за операцию и O(1) за запрос. Мы храним элементы в неявном трэпе (или в некоторой другой подобной декартовой древовидной структуре), который разрешает вставки, удаления и доступ по индексу в формате O(log n). После того, как мы выполним все операции, мы проведем итерацию по неявному трепу и создадим таблицу положений элементов. Затем мы можем ответить на вопросы в O(1), как описано в ответе Самгака.

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

Измените структуру списка для хранения начальной позиции каждого элемента, например, для сохранения кортежа индекса, значения вместо значения для каждого элемента: 

 ['a', 'x', 'b', 'w', 'e']

становится 

 [{'a', 0}, {'x', 1}, {'b', 2}, {'w', 3}, {'e', 4}]

Затем запустите вставки и удаления, присваивая каждой новой вставке индекс -1, чтобы указать, что ее нет в исходном списке: 

 [{'j', -1}, {'x', 1}, {'b', 2}, {'u', -1}, {'w', 3}]

Теперь создайте массив 'newIndexArray', равный исходному размеру списка, инициализируйте все значения -1, а затем выполните итерации по новому списку, увеличивая счетчик, начиная с нуля, чтобы отслеживать новую позицию. Для каждого элемента установите: 

 newIndexArray[elementTuple.Item2] = counter

newIndexArray теперь будет связываться со следующими значениями: 

 newIndexArray[0] = -1
 newIndexArray[1] = 1
 newIndexArray[2] = 2
 newIndexArray[3] = 4
 newIndexArray[4] = -1

-1 означает, что элемент, который был первоначально в этой позиции, был удален.

Алгоритм: O (N) для всего списка или O (1) на элемент. Существует O (1) дополнительная стоимость за вставку и (инициализация индекса -1)

...