Минимум смежных свопов, необходимых для получения K-го наименьшего числа, большего заданного числа

Для данной числовой строки S размера N и положительного целого числа K задача состоит в том, чтобы найти минимальное количество смежных перестановок, необходимых в S для получения K-й наименьшей числовой строки, большей, чем заданная строка.

Примеры:

Input: S = “11112”, K = 4
Output: 4
Explanation:
The K^th(= 4^th) smallest numeric string which is greater than the given string is “21111”. The sequence of adjacent swap to reach the string “21111” is “11112” -> “11121” -> “11211″ -> “12111″ -> “21111″.
Therefore, the minimum number of adjacent swaps required is 4.

Input: S = “12345”, K = 1
Output: 1

Подход: Данная проблема может быть решена с использованием жадного подхода. Выполните следующие шаги, чтобы решить проблему:

• Сохраните копию текущей числовой строки в переменной, скажем, res .
• Создайте переменную, скажем, totalSwaps , которая хранит минимальные требуемые свопы.
• Поскольку требуется K-е наибольшее число, это утверждение эквивалентно поиску K-й перестановки, начиная с текущей строки.
• Найдите K-ю перестановку с помощью функции next_permutation().
• Перебрать диапазон [0, N), используя переменную i , и выполнить следующие задачи:
  • Если res[i] не равно str[i] , тогда инициализируйте переменную start как i+1 и пройдите цикл while, пока res[i] не будет равно str[start] и увеличьте значение i на 1.
  • Повторяйте цикл до тех пор, пока i не станет равным start , и поменяйте местами значения str[start] и str[start – 1] , уменьшите значение start на 1 и увеличьте значение totalSwaps на 1 .
• После выполнения вышеуказанных шагов выведите значение totalSwaps в качестве ответа.

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

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