Minimum Adjacent Swaps to Reach the Kth Smallest Number
To solve this problem, we need to simulate the next permutation operation k
times and then count the swaps needed to turn num
into the kth wonderful integer.
|
|
In this code, next_permutation
is a helper function that generates the next lexicographical permutation of arr
. It works by identifying the last “ascending” position in arr
, swapping this position with the smallest larger element in the rest of the array, and then reversing the tail of the array.
The main part of getMinSwaps
transforms num
into a list of characters, applies next_permutation
k
times, and then counts the number of adjacent swaps needed to turn num
into the kth wonderful integer. This count is achieved by a linear scan and moving the j
pointer until it finds the target element and then shifting the subarray one place to the right and moving the target element to the leftmost position. The distance that j
has moved is the number of swaps made.