Как создать последний недавно использованный кэш?

Как создать последний недавно использованный кеш?

Предположим, вы посетили какие-то предметы. Вам необходимо разработать структуру данных для хранения этих элементов. Каждый элемент связан с временем последнего посещения.

Каждый раз, когда вы посещаете элемент, проверяйте его в структуре данных. Если элемент был в кеше, обновите время его посещения. В противном случае вставьте его в кеш. Размер кеша фиксированный, если он заполнен, удалите самый старый элемент.

Мое решение:

1. Используйте карту

2. Инициализация: отсортируйте карту с помощью f (visitTime) в порядке убывания. O (nlg n)

3. Если элемент посещается, найдите его на карте с помощью O (lg n).

4. Если он был на карте, обновите время O (1). Отсортируйте карту O (lg n).

5. Если нет, вставьте его на карту и отсортируйте. O (lg n)

6. Если размер карты> фиксированного размера, удалить последний элемент O (1).

Другое решение:

1. Используйте хеш-таблицу

2. Отсортируйте O (n lgn).

3. Если предмет посещен, найдите его в талбе с помощью O (1).

4. Если оно было в таблице, обновите время O (1). Сортировать таблицу O (n lg n).

5. Если нет, вставьте его в таблицу и затем отсортируйте. O (n lg n)

6. Если размер таблицы> фиксированного размера, удалить последний элемент O (1).

Есть ли лучшие решения? На) ?