1505. 最多 K 次交换相邻数位后得到的最小整数

https://leetcode-cn.com/problems/minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits/

这题目的一些关键难点我都考虑到了,但是在实现步骤上出现了差错。

所以这个算法的难点是,我们要维护一个数据结构,当前移 nums[j] 这个数字的时候,知道已经有多少个数字(比如k)是 nums[i] (i<j) 的。那么这次移动 nums[j] 这个数字的话,cost就是 j-k.

其实这个问题完全可以转换成为求解前缀和

如果将这个问题转换成为前缀和的话,那么又会多了两种数据结构:区间树和Fenwick树,其实是一个思想,但是Fenwick写起来更简单。我之前写过一篇 BIT/Fenwick树 的文章。

代码如下,二分搜索或者是Fenwick可以作为一个抽象策略存在:

class Solution:
    class BIT:
        def __init__(self, n):
            self.n = n
            self.values = [0] * (n + 1)

        def update(self, x):
            x += 1
            n = self.n
            while x <= n:
                self.values[x] += 1
                x += (x & -x)

        def query(self, x):
            x += 1
            ans = 0
            while x > 0:
                ans += self.values[x]
                x -= (x & -x)
            return ans

    class BS:
        def __init__(self, n):
            self.bs = []

        def update(self, x):
            import bisect
            bisect.insort(self.bs, x)

        def query(self, x):
            import bisect
            return bisect.bisect(self.bs, x)

    def minInteger(self, num: str, k: int) -> str:

        qs = [[] for _ in range(10)]
        buf = []
        for i in reversed(range(len(num))):
            c = int(num[i])
            qs[c].append(i)

        BSClass = self.BIT
        bs = BSClass(len(num))
        while k and len(buf) < len(num):
            ok = False
            for i in range(10):
                if not qs[i]: continue
                q = qs[i][-1]
                j = bs.query(q)
                # print(q, j)
                if (q - j) <= k:
                    qs[i].pop()
                    bs.update(q)
                    k -= (q - j)
                    buf.append(q)
                    ok = True
                    break
            if not ok: break

        used = set(buf)
        ans = []
        for q in buf:
            ans.append(num[q])
        for i in range(len(num)):
            if i in used: continue
            ans.append(num[i])

        ans = ''.join(ans)
        return ans