You are given a string num
, representing a large integer, and an integer k
.
We call some integer wonderful if it is a permutation of the digits in num
and is greater in value than num
. There can be many wonderful integers. However, we only care about the smallest-valued ones.
- For example, when
num = "5489355142"
:- The 1st smallest wonderful integer is
"5489355214"
. - The 2nd smallest wonderful integer is
"5489355241"
. - The 3rd smallest wonderful integer is
"5489355412"
. - The 4th smallest wonderful integer is
"5489355421"
.
- The 1st smallest wonderful integer is
Return the minimum number of adjacent digit swaps that needs to be applied to num
to reach the kth
smallest wonderful integer.
The tests are generated in such a way that kth
smallest wonderful integer exists.
Example 1:
Input: num = "5489355142", k = 4 Output: 2 Explanation: The 4th smallest wonderful number is "5489355421". To get this number: - Swap index 7 with index 8: "5489355142" -> "5489355412" - Swap index 8 with index 9: "5489355412" -> "5489355421"
Example 2:
Input: num = "11112", k = 4 Output: 4 Explanation: The 4th smallest wonderful number is "21111". To get this number: - Swap index 3 with index 4: "11112" -> "11121" - Swap index 2 with index 3: "11121" -> "11211" - Swap index 1 with index 2: "11211" -> "12111" - Swap index 0 with index 1: "12111" -> "21111"
Example 3:
Input: num = "00123", k = 1 Output: 1 Explanation: The 1st smallest wonderful number is "00132". To get this number: - Swap index 3 with index 4: "00123" -> "00132"
Constraints:
2 <= num.length <= 1000
1 <= k <= 1000
num
only consists of digits.
Solution: Next Permutation + Greedy
Time complexity: O(k*n + n^2)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { public: int getMinSwaps(string s, int k) { string t(s); while (k--) next_permutation(begin(t), end(t)); const int n = s.length(); int ans = 0; for (int i = 0; i < n; ++i) { if (s[i] == t[i]) continue; for (int j = i + 1; j < n; ++j) { if (s[i] != t[j]) continue; ans += j - i; t = t.substr(0, i + 1) + t.substr(i, j - i) + t.substr(j + 1); break; } } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment