Структура данных для перестановок в Java

Question

Мне нужно хранить перестановку из n целых чисел и иметь возможность вычислять как перестановку значения, так и обратную операцию за эффективное время.

Т.е. мне нужно сохранить переупорядочение значений [0...n-1] таким образом, чтобы я мог запросить позицию (i) и значение (j) (при 0 <= i,j <= n).

С примером - предположим, у нас есть следующая перестановка значений:

• [7,2,3,6,0,4,8,9,1,5]

Мне нужны следующие операции:

• позиция (7) = 9
• значение (9) = 7

Я знаю библиотеки в C++ для этого, такие как: https://github.com/fclaude/libcds2

Есть ли какая-либо структура или библиотека в Java, которая позволяет делать это и является эффективной в пространстве и времени?

Answer 1

Если дубликатов нет, List Интерфейс будет соответствовать вашим потребностям.

Он предоставляет следующие методы:

• List#get(index) возвращает элемент с индексом index
• List#indexOf(element) возвращает индекс первой встреченной element