在对字符串 num 进行数位交换的过程中,它的长度(数位的个数)不会发生变化。因此,数值最小的整数就等价于字典序最小的整数。
要想得到在 k 次交换内字典序最小的整数,我们可以「贪心」地从 num 的最高位开始考虑,即希望 num 的最高位尽可能小。我们可以依次枚举 0 \sim 9,对于当前枚举到的数位 x,判断是否可以将某个位置上的 x 通过最多 k 次交换移动到最高位。由于每一次交换只能交换相邻位置的两个数字,因此将一个距离最高位为 s 的数位移动到最高位,需要 s 次交换操作。例如当 num} = 97620 时,0 与最高位的距离为 4,我们可以通过 4 次交换操作把 0 移动到最高位:
如果有多个 x 与最高位的距离小于等于 k,那么我们该如何进行选择呢?直观来看,我们应该选择最近的那个 x,这样需要交换的次数就最少。
我们接下来考虑次高位。与最高位类似,我们选择最小的数位 x,使得它与次高位的距离不超过 k’,其中 k’ 是 k 扣除最高位交换后的剩余次数。考虑上面 num} = 97620 的例子,此时我们应当选择 x=2 交换至次高位。然而我们发现,经过第一次的交换操作,2 所在的位置发生了变化!在 num 中,2 与次高位的距离为 2,而将 0 交换至最高位后,2 与次高位的距离增加了 1,变为 3。这是因为 0 从 2 的后面「转移」到了 2 的前面,使得 2 向后移动了一位。因此,x 实际所在的位置,等于 x 初始时在 num 中的位置,加上 x 后面发生交换的数位个数。这里的「x 后面发生交换的数位个数」,就可以使用树状数组进行维护。
因此,我们从高到低考虑每一位,对于每一位找出距离该位置小于等于 k(剩余的交换次数)且最小的数位,记录该数位的位置、完成交换并更新 k 值。注意到如果我们枚举到了恰好在这一位上的那个数位,计算出的距离为 0,同样小于等于 k。因此我们总能找到一个满足要求的数位进行交换。
算法
对于未接触过树状数组的读者来说,本题有较大的难度。这里我们给出解决本题的算法框架:
我们用 pos}[x] 按照从高位到低位的顺序,存放所有 x 在 num 中出现的位置;
我们从高到低遍历每一个位置。对于位置 i,我们从小到大枚举交换的数位 x。pos}[x] 中的首元素即为与当前位置距离最近的 x 的位置:
记 u 为 pos}[x] 中的首元素,那么 num}[u](也就是 x)当前实际所在的位置,等于 u 加上 u 后面发现交换的数位个数。我们使用树状数组查询区间 [u+1, n],得到结果 behind,其中 n 是 num 的长度。那么 num}[u] 与位置 i 的实际距离即为 u + \textit{behind} - i。
如果该距离小于等于 k,那么我们就可以将 x 交换到位置 i。我们使用树状数组更新单点 u,将对应的值增加 1,表示该位置的数位发生了交换。随后我们还需要更新 k 值以及将 u 从 pos 中移除。
在遍历结束后,我们就得到了答案。
注意:树状数组的下标一般从 1 开始,而给定的字符串 num 的下标从 0 开始,因此需要设置 1 的下标偏移量。
classSolution: defminInteger(self, num: str, k: int) -> str: n = len(num) pos = [list() for _ inrange(10)] for i inrange(n - 1, -1, -1): pos[ord(num[i]) - ord('0')].append(i + 1) ans = "" bit = BIT(n) for i inrange(1, n + 1): for j inrange(10): if pos[j]: behind = bit.queryRange(pos[j][-1] + 1, n) dist = pos[j][-1] + behind - i if dist <= k: bit.update(pos[j][-1]) pos[j].pop() ans += str(j) k -= dist break return ans