题目描述

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

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

例如，num = "5489355142"：
第 1 个最小妙数是 "5489355214"
第 2 个最小妙数是 "5489355241"
第 3 个最小妙数是 "5489355412"
第 4 个最小妙数是 "5489355421"

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

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

样例

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

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

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

限制

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

算法1

(暴力) $O(nk + n^2)$

1. 先通过 next_permutation 求出第 k 小妙数。
2. 然后匹配两个字符串，遇到不一致的位置时，暴力在后边寻找第一个相同的数字，然后移动整个区间进行匹配。同时累加答案。

时间复杂度

• 每次 next_permutation 的时间复杂度为 $O(n)$。
• 暴力匹配最坏情况下需要 $O(n^2)$ 的时间。
• 故总时间复杂度为 $O(nk + n^2)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储字符串的备份。

C++ 代码

class Solution {
public:
    int getMinSwaps(string num, int k) {
        string num_backup = num;

        while (k--)
            next_permutation(num.begin(), num.end());

        const int n = num.size();

        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (num_backup[i] == num[i])
                continue;

            int p = -1;
            for (int j = i + 1; j < n; j++)
                if (num_backup[j] == num[i]) {
                    p = j;
                    break;
                }

            ans += p - i;
            for (int j = p - 1; j >= i; j--)
                num_backup[j + 1] = num_backup[j];
        }

        return ans;
    }
};

算法2

(逆序对) $O(nk + n \log n)$

1. 暴力求出第 k 小的妙数。
2. 记录原始字符串的数字映射下标，然后对应回新的字符串，求新的字符串的逆序对的个数。

时间复杂度

• 求第 k 小的妙数的时间复杂度为 $O(nk)$。
• 树状数组求逆序对的时间复杂度为 $O(n \log n)$。
• 故总时间复杂度为 $O(nk + n \log n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储树状数组。

C++ 代码

class Solution {
private:
    vector<int> f;

    void add(int x, int n, int y) {
        for (; x <= n; x += x & -x)
            f[x] += y;
    }

    int query(int x) {
        int tot = 0;
        for (; x; x -= x & -x)
            tot += f[x];
        return tot;
    }

public:
    int getMinSwaps(string num, int k) {
        const int n = num.size();
        vector<vector<int>> pos(10);
        for (int i = 0; i < n; i++)
            pos[num[i] - '0'].push_back(i + 1);

        while (k--)
            next_permutation(num.begin(), num.end());

        f.resize(n + 1, 0);

        int ans = 0;
        for (int i = n - 1; i >= 0; i--) {
            int x = pos[num[i] - '0'].back();
            pos[num[i] - '0'].pop_back();

            ans += query(x - 1);
            add(x, n, 1);
        }

        return ans;
    }
};