1505. 最多 K 次交换相邻数位后得到的最小整数
1505. 最多 K 次交换相邻数位后得到的最小整数
转载请以链接形式标明出处： 本文出自:103style的博客
原题链接 – https://leetcode-cn.com/problems/minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits/
给你一个字符串 num 和一个整数 k 。其中，num 表示一个很大的整数，字符串中的每个字符依次对应整数上的各个 数位 。
你可以交换这个整数相邻数位的数字 最多 k 次。
请你返回你能得到的最小整数，并以字符串形式返回。
示例 1：
输入：num = "4321", k = 4
输出："1342"
解释：4321 通过 4 次交换相邻数位得到最小整数的步骤如上图所示。示例 2：
输入：num = "100", k = 1
输出："010"
解释：输出可以包含前导 0 ，但输入保证不会有前导 0 。示例 3：
输入：num = "36789", k = 1000
输出："36789"
解释：不需要做任何交换。示例 4：
输入：num = "22", k = 22
输出："22"示例 5：
输入：num = "9438957234785635408", k = 23
输出："0345989723478563548"提示：
1 <= num.length <= 30000num只包含 数字 且不含有 前导 0 。1 <= k <= 10^9
题目来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits
目录： 理解题意 → 递归解法 → 优化递归 → 优化到O(N logN)
理解题意
首先根据题目描述，我们可以得到： 要想在移动 k 次之后得到最小的数， 必须每次移动尽可能的在K次内，把从 0 开始到 9 的数移动到使前面没有比它大的数字的位置。
比如： num = 4321, k = 4.
我们能找到的最小的数是 1, 把 1 移动到开头需要移动 3 次。
所以移动之后得到： num = 1432, k = 4 - 3 = 1;
然后从 1 后面开始，我们能找到的 2， 把 2 移动到 1 后面需要移动 2 次， 但是 k = 1, 所以我们得找下一个小的数。 我们找到了 3，然后把 3 移动到 1 后面需要 移动 1 次， k = 1, 刚好可以。
所以移动之后得到： num = 1342, k = 1 - 1 = 0;
因为 k = 0 不能移动了， 所以我们直接返回 1342。
递归解法（超出时间限制）
所以代码我们可以用 递归 直接这样写, 但是在第48个测试用例的时候会提示 超出时间限制。
我们来分析下时间复杂度，
num.indexOf(c) 是 O(N), subString 也是 O(N),
一共执行了 N 次， 所以时间复杂度是 O(N^2).
代码来自评论区
public String minInteger(String num, int k) {
if (k == 0) return num;
for (char c = '0'; c <= '9'; c++) {
int i = num.indexOf(c);
if (i >= 0) {
if (i <= k) {
return c + minInteger(num.substring(0, i) + num.substring(i + 1), k - i);
}
}
}
return num;
}优化递归
对于递归方法的 indexOf 和 substring 我们可以怎么优化呢？
因为我们每次都要从 0 到 9 去获取其在 num 对应的位置, 所以我们可以先记录他们的位置， 可以通过下面的代码一次遍历就能获取到 0 - 9 在 num中的所有位置。可以把每次查找位置的时间复杂度从 O(N) 降到 O(1).
LinkedList<Integer>[] list = new LinkedList[10];
for (int i = 0; i < 10; i++) {
list[i] = new LinkedList<>();
}
int len = num.length();
char[] arr = num.toCharArray();
for (int i = 0; i < len; i++) {
list[arr[i] - '0'].add(i);
}这样我们保存的是 0 - 9 在 num中的原始位置。
我们再来看个示例 num = 4132, k = 4.
把 4 移动到最前面是 0 次， 1 是1次，3 是 2次，2 是 3次
当我们移动 1 之后 得到 num = 1432, k = 3.
此时 1 是已经确定的相当于只是处理 432， 此时我们和开始的 4132 相比把每个数 移动到最前面的次数变成了:
把 4 移动到最前面是 0 次， 3 是 1次，2 是 2次.
我们发现， 每一移动完一个字符，他后面的字符最前面的次数就会 减1。
这样我们就可以记录每次移动的字符后面字符让后面的字符的移动次数减一。
对于substring 我们可以记录那些字符已经用过了, 这样就可以直接在原字符上操作了，不需要利用substring了。
代码如下， 这样能通过所有的测试用例了，但是 执行用时：1131 ms， 还是比较慢的， 我们还可以继续优化。
// O(N^2)time
// O(N)space
public String minInteger(String num, int k) {
//记录0 - 9 在 num中的位置
LinkedList<Integer>[] list = new LinkedList[10];
for (int i = 0; i < 10; i++) {
list[i] = new LinkedList<>();
}
int len = num.length();
char[] arr = num.toCharArray();
for (int i = 0; i < len; i++) {
list[arr[i] - '0'].add(i);
}
//记录结果， 添加已经移动过的字符
StringBuilder res = new StringBuilder();
//记录 当前位置 前面由多少个字符已经移动过
int[] offset = new int[len];
outer:
// k > 0 说明我们 可以移动， res.length() < len 说明还有字符未被移动
while (k > 0 && res.length() < len) {
for (int i = 0; i < 10; i++) {
if (list[i].isEmpty()){
//num中没有这个字符
continue;
}
//获取字符的下标 减去 前面已经移动过的字符 得到 它移动到最前面需要的次数
int move = list[i].getFirst() - offset[list[i].getFirst()];
if (move > k) {
//比 K 大，则找下一个数字
continue ;
}
//更新 k的值
k -= move;
//获取这个字符的首个位置， 并把它从保存位置的链表中移除，因为我们已经用过了，不能再用
int index = list[i].removeFirst();
//添加到结果中
res.append(arr[index]);
//修改num中这个位置为 字符 0， 表示我们已经用过了。
arr[index] = 0;
//将 index 后面的字符的需要减去的移动次数 + 1
for (int j = index + 1; j < len; j++) {
offset[j]++;
}
//继续从 0 开始找 移动次数小于 k 的字符
continue outer;
}
}
//如果 k 比较小， 就会存在 还有字符未被移动， 我们按原顺序依次添加
for (int i = 0; i < len; i++) {
if (arr[i] != 0) {
res.append(arr[i]);
}
}
return res.toString();
}优化到 O(N*logN)
上面的代码， 每次移动一个字符之后，需要对后面的所有字符记录前面移动的字符 加 1。
那我们也可以直接保存 移动过字符的位置，找字符时，通过二分查找 已经移动过的位置记录中 有多少个 比当前位置小。
而且我们字符最多移动 1 + 2 + … + n-1 = (n - 1) * n / 2 次， 所以当 k >= (n -1) * n / 2 时， 我们可以直接对字符按升序排序。
代码如下：执行用时：57 ms
//O(N * logN)time
//O(N)space
public String minInteger(String num, int k) {
//记录0 - 9 在 num中的位置
LinkedList<Integer>[] list = new LinkedList[10];
for (int i = 0; i < 10; i++) {
list[i] = new LinkedList<>();
}
int len = num.length();
char[] arr = num.toCharArray();
for (int i = 0; i < len; i++) {
list[arr[i] - '0'].add(i);
}
if (k >= (len - 1) * len / 2) {
Arrays.sort(arr);
return new String(arr);
}
//记录移动的字符位置
List<Integer> record = new ArrayList<>();
//记录结果， 添加已经移动过的字符
StringBuilder res = new StringBuilder();
outer:
while (k > 0 && res.length() < len) {
for (int i = 0; i < 10; i++) {
if (list[i].isEmpty()) {
continue;
}
//找到移动的字符位置中有 多少个比当前位置小
int index = findIndex(record, list[i].getFirst());
int move = list[i].getFirst() - index;
if (move > k) {
continue;
}
//更新 k的值
k -= move;
//获取这个字符的首个位置， 并把它从保存位置的链表中移除，因为我们已经用过了，不能再用
int pos = list[i].removeFirst();
//把当前 位置 添加到 已经移动过的位置列表中
record.add(index, pos);
res.append(i);
arr[pos] = 0;
continue outer;
}
}
for (int i = 0; i < len; i++) {
if (arr[i] != 0) {
res.append(arr[i]);
}
}
return res.toString();
}
/**
* 二分查找比 value小的个数
*/
int findIndex(List<Integer> list, int value) {
int l = 0, r = list.size();
while (l < r) {
int mid = (l + r) >> 1;
if (list.get(mid) < value) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}以上，如果有描述错误的，请路过的大佬指出来。
树状数组 Fenwich Tree 解法：
腾讯云开发者
