Минимальное количество соседних перестановок, необходимых для преобразования перестановки в другую перестановку по заданному условию

Дана перестановка P размера N , имеющая значения от 1 до N. задача состоит в том, чтобы найти минимальное необходимое количество соседних свопов, такое что для всех i в диапазоне [1, N] , P [i] не равно i .
Примеры:

Input: P = [1, 4, 3, 5, 2] 
Output: 2 
Explanation: 
Here P = [1, 4, 3, 5, 2] at index 1, 2, 3, 4, 5. As we can see, P[1] = 1 and P[3] = 3. Hence, we need to get rid of this invariant. 
Swap 1: Swap index 1 and index 2 => [4, 1, 3, 5, 2] 
Swap 2: Swap index 2 and index 3 => [4, 3, 1, 5, 2] 
The final array has no i where P[i] = i. Hence, a minimum of 2 swaps is required.
Input: P = [1, 2, 4, 9, 5, 8, 7, 3, 6] 
Output: 3 
Explanation: 
Swap 1: Swap index 1 and index 2 => [2, 1, 4, 9, 5, 8, 7, 3, 6] 
Swap 2: Swap index 5 and index 6 => [2, 1, 4, 9, 8, 5, 7, 3, 6] 
Swap 2: Swap index 7 and index 8 => [2, 1, 4, 9, 8, 5, 3, 7, 6] 
Hence, a minimum of 3 swaps is required. 
 

Подход: Рассмотрим позиции, в которых P [i] = i , обозначим X, а другие позиции - O. Ниже приведены три основных замечания по этому вопросу:

• Если значения в любых двух смежных индексах перестановки имеют форму XO , мы можем просто поменять местами два индекса, чтобы получить «OO».
• Если значения в любых двух смежных индексах перестановки имеют форму XX , мы можем просто поменять местами два индекса, чтобы получить «OO».
• Если значения в любых двух смежных индексах перестановки имеют форму OX , это просто «XO» или «XX», когда указатель достигает индекса в X.

Ниже приведены шаги:

1. Итерируем от 1 до N - 1 и проверяем, что P [i] = i, тогда мы просто меняем местами (P [i], P [i + 1]) , в противном случае продолжаем процесс для следующих соседних пар.
2. Угловой случай для данного вопроса - когда i = N , если P [i] = i, то мы меняем местами (P [i], P [i - 1]) .

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

Сложность времени: O (N)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.