Java-программа для максимального увеличения количества соответствующих одинаковых элементов в заданных перестановках с использованием циклических поворотов

Даны две перестановки P1 и P2 чисел от 1 до N , задача состоит в том, чтобы найти максимальное количество соответствующих одинаковых элементов в данных перестановках, выполняя циклический сдвиг влево или вправо на P1 .
Примеры:

Input: P1 = [5 4 3 2 1], P2 = [1 2 3 4 5] 
Output: 1 
Explanation: 
We have a matching pair at index 2 for element 3.
Input: P1 = [1 3 5 2 4 6], P2 = [1 5 2 4 3 6] 
Output: 3 
Explanation: 
Cyclic shift of second permutation towards right would give 6 1 5 2 4 3, and we get a match of 5, 2, 4. Hence, the answer is 3 matching pairs. 
 

Наивный подход: наивный подход заключается в проверке каждого возможного сдвига как влево, так и вправо, подсчета количества совпадающих пар путем перебора всех сформированных перестановок.
Временная сложность: O(N ² )
Вспомогательное пространство: O(1)
Эффективный подход. Описанный выше наивный подход можно оптимизировать. Идея состоит в том, чтобы каждый элемент хранил меньшее расстояние между позициями этого элемента с левой и правой сторон в отдельных массивах. Следовательно, решение задачи будет вычисляться как максимальная частота элемента из двух разделенных массивов. Ниже приведены шаги:

1. Сохраните положение всех элементов перестановки P2 в массиве (например, store[] ).
2. Для каждого элемента в перестановке P1 сделайте следующее:
   • Найдите разницу (скажем, diff ) между позицией текущего элемента в P2 и позицией в P1 .
   • Если diff меньше 0, обновите diff до (N – diff) .
   • Сохраните частоту текущей разности различий на карте.
3. После вышеуказанных шагов максимальная частота, сохраняемая в карте, равна максимальному количеству равных элементов после поворота на P1 .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)

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