1850-邻位交换的最小次数(Minimum Adjacent Swaps to Reach the Kth Smallest Number)

原文链接: https://leetcode-cn.com/problems/minimum-adjacent-swaps-to-reach-the-kth-smallest-number

英文原文

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":

<ul>
    <li>The 1<sup>st</sup> smallest wonderful integer is <code>&quot;5489355214&quot;</code>.</li>
    <li>The 2<sup>nd</sup> smallest wonderful integer is <code>&quot;5489355241&quot;</code>.</li>
    <li>The 3<sup>rd</sup> smallest wonderful integer is <code>&quot;5489355412&quot;</code>.</li>
    <li>The 4<sup>th</sup> smallest wonderful integer is <code>&quot;5489355421&quot;</code>.</li>
</ul>
</li>

Return the minimum number of adjacent digit swaps that needs to be applied to num to reach the k^th smallest wonderful integer.

The tests are generated in such a way that k^th smallest wonderful integer exists.

Example 1:

Input: num = "5489355142", k = 4
Output: 2
Explanation: The 4^th 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 4^th 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 1^st 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.

中文题目

给你一个表示大整数的字符串 num ，和一个整数 k 。

如果某个整数是 num 中各位数字的一个排列且它的 值大于 num ，则称这个整数为妙数。可能存在很多妙数，但是只需要关注 值最小 的那些。

例如，num = "5489355142" ：

<ul>
    <li>第 1 个最小妙数是 <code>"5489355214"</code></li>
    <li>第 2 个最小妙数是 <code>"5489355241"</code></li>
    <li>第 3 个最小妙数是 <code>"5489355412"</code></li>
    <li>第 4 个最小妙数是 <code>"5489355421"</code></li>
</ul>
</li>

返回要得到第 k 个 最小妙数 需要对 num 执行的 相邻位数字交换的最小次数 。

测试用例是按存在第 k 个最小妙数而生成的。

示例 1：

输入：num = "5489355142", k = 4
输出：2
解释：第 4 个最小妙数是 "5489355421" ，要想得到这个数字：
- 交换下标 7 和下标 8 对应的位："5489355142" -> "5489355412"
- 交换下标 8 和下标 9 对应的位："5489355412" -> "5489355421"

示例 2：

输入：num = "11112", k = 4
输出：4
解释：第 4 个最小妙数是 "21111" ，要想得到这个数字：
- 交换下标 3 和下标 4 对应的位："11112" -> "11121"
- 交换下标 2 和下标 3 对应的位："11121" -> "11211"
- 交换下标 1 和下标 2 对应的位："11211" -> "12111"
- 交换下标 0 和下标 1 对应的位："12111" -> "21111"

示例 3：

输入：num = "00123", k = 1
输出：1
解释：第 1 个最小妙数是 "00132" ，要想得到这个数字：
- 交换下标 3 和下标 4 对应的位："00123" -> "00132"

提示：

2 <= num.length <= 1000
1 <= k <= 1000
num 仅由数字组成

通过代码

高赞题解

这道题分为两个部分：求第 $k$ 个妙数、求两个排列的距离。

一：求第k个妙数

求下一个妙数相当于求比当前数大的最近的排列，求比当前数大的最近的排列是 556. 下一个更大元素 III 这道题，直接求对字符串调用next_permutation即可。这道题要求第 $k$ 个妙数，相当于求下 $k$ 个排列，直接暴力调用 $k$ 次next_permutation就可解决。

二：求排列间距离

求出了第 $k$ 个妙数后，接下来要求出原数经过几次交换能得到这个数，这相当于求两个排列间的距离。

求两个排列间的距离可以先考虑一个简单情况，排列中字符各不相同。

这种情况可以直接把字符映射为下标，比如求"bdca"和"cdba"之间的距离，可以把第一个字符串中的字符映射为下标，也就是
$$b \rightarrow 0,d \rightarrow 1,c \rightarrow 2,a \rightarrow 3$$
然后把第二个字符串按这个映射关系替换为"2103"。这样把第二个字符串变为第一个就相当于进行排序，而交换相邻元素来进行排序的方法就是冒泡排序，而冒泡排序的交换次数就是逆序对个数，逆序对问题可以 $O(nlog n)$ 解决，这题数据量不大，用 $O(n^2)$ 的暴力解法也可解决。

如果字符有重复呢？这相当于一个字符有多种可能的映射，由于要让交换次数尽可能小，所以贪心地让映射的下标升序就行。

比如对于字符串"abacda"，字符 $a$ 有 $a \rightarrow 0、2、5$ 这 $3$ 个映射到的下标，那么在替换第二个字符串"dcabaa"中的字符 $a$ 时，从左到右依次替换为 $0、2、5$ 即可，得到"dc0b25"，这样才能使这几个相同的字符间不发生交换，交换次数最小。

代码

[]
class Solution {
public:
    int getMinSwaps(string num, int k) {
        const int n = num.size();
        // 第 k 个妙数
        string per = num;
        for (int i = 0;i < k;++i)
            next_permutation(per.begin(), per.end());
        // 进行下标映射
        vector<int> map[10];
        for (int i = 0;i < n;++i)
            map[num[i] - '0'].push_back(i);
        int idx[10] = {};
        vector<int> arr(n);
        for (int i = 0;i < n;++i)
            arr[i] = map[per[i] - '0'][idx[per[i] - '0']++];
        // 暴力求逆序对个数 O(n^2)
        int ans = 0;
        for (int i = 0;i < n;++i)
            for (int j = i + 1;j < n;++j)
                if (arr[i] > arr[j]) ++ans;
        return ans;
    }
};

[]
class Solution {
public:
    int getMinSwaps(string num, int k) {
        const int n = num.size();
        // 第 k 个妙数
        string per = num;
        for (int i = 0;i < k;++i)
            next_permutation(per.begin(), per.end());
        // 进行下标映射
        vector<int> map[10];
        for (int i = 0;i < n;++i)
            map[num[i] - '0'].push_back(i);
        int idx[10] = {};
        vector<int> arr(n);
        for (int i = 0;i < n;++i)
            arr[i] = map[per[i] - '0'][idx[per[i] - '0']++];
        // 树状数组求逆序对个数 O(nlogn)
        vector<int> tree(n + 1);
        int ans = 0;
        for (int i = n - 1;0 <= i;--i) {
            for (int j = arr[i];j > 0;j -= j & -j) ans += tree[j]; // 查询
            for (int j = arr[i] + 1;j <= n;j += j & -j) ++tree[j]; // 更新
        }
        return ans;
    }
};

统计信息

通过次数	提交次数	AC比率
2493	4089	61.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途