Структура данных для сохранения наименьших значений в строке

Question

Скажем, у нас есть строка символов (скажем, их значения указаны в диапазоне 0--255 для ASCII и диапазоне 0--65,535).

Вот список задач может быть применен:

1. отслеживает показатели каждого уникального характера (последние один);
2. получить символ с наименьшим index;
3. обновите структуру данных (удалите тот, который был возвращен в 2, и добавьте новый).

Вот пример, а индекс я идет от 0 до 17

aabbaaaacccddccccc 

мы можем отслеживать строку онлайн, как это, где целое число в скобках является индексом соответствующий характер:

• а (0)
• а (1) б (2)
• а (1) б (3)
• ...
• а (7) б (3)
• а (7) б (3) с (8)
• ...
• a (7) b (3) c (10) Теперь мы читаем символ 'd', и нам нужно обновить структуру данных с помощью правила, скажем, удалить элемент с наименьшим индексом: b (3) и добавить д (11)
• а (7) д (11) с (10)
• ...

Мы можем использовать HashMap для отслеживания показателей каждого уникального характера:

Map<Character, Integer> myMap = new HashMap<>(m); 
myMap.put(new Character(input.charAt(j)), j); 

Но когда мы хотим получить символ с наименьшим индексом, мы можем пройти через карту один-на-один, который не так эффективен, как я хотел.

Мы можем использовать приоритетную очередь для хранения элементов, что дало мне время O (1) для получения наименьшего элемента; но я не могу обновить очередь приоритетов так же, как и карту.

Есть идеи?

Answer 1

Как и ваша карта myMap от символа до положения, вы также можете обновить SortedMap с позиции на символ.

Для каждого символа с входом Вы:

1. Посмотрите с в MyMap найти свой индекс я
2. Если он присутствует, то удалить ключ я из SortedMap
3. Изменение MyMap [с ], чтобы указать на новый индекс
4. Изменение SortedMap [новый индекс], чтобы указать с

Если вы хотите, чтобы найти элемент с smalles t index, вы можете просто посмотреть на первый элемент SortedMap. С SortedMap это эффективная операция.