5455. 最多 K 次交换相邻数位后得到的最小整数 [hard]

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 <= 30000
num 只包含数字且不含有前导 0 。
1 <= k <= 10^9

通过次数691 | 提交次数2,880

Second Try

2020-07-05

暴力法竟然还有另一种写法，每次直接按0-9的顺序把存在的往前扔就可以了。而且也不用提前判断num和k,最后结果也没问题。

# 竟然还有另一个写法
class Solution(object):
    def minInteger(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        # 复杂度应该是 N^2? 每次使用not in和index判断都是O(N),然后总共N次循环，共O(N^2)
        fixed = ""
        notfixed = num
        starti = 0
        while k >= 0 and len(notfixed):
            # 不能使用starti进行跟踪，因为当前的i距离太远，不代表以后仍然太远
            # for i in range(starti, 10):
            for i in range(0, 10):  
                # print(i, k, notfixed)
                if str(i) not in notfixed:  # 各种O(N)..
                    continue
                
                idx = notfixed.index(str(i))
                if idx <= k:
                    fixed += str(i)
                    notfixed = notfixed[:idx] + notfixed[idx + 1: ]
                    k -= idx
                    starti = i  # 有可能还有相同的数字
                    break
        return fixed + notfixed
            

执行用时：1456 ms, 在所有 Python 提交中击败了100.00%的用户
内存消耗：13.1 MB, 在所有 Python 提交中击败了100.00%的用户

继续提前判断k和n的关系，速度还能更快

class Solution(object):
    def minInteger(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        # 复杂度应该是 N^2? 每次使用not in和index判断都是O(N),然后总共N次循环，共O(N^2)
        if k >= (1 + len(num)) * len(num) / 2:
            return ''.join(sorted(num))
            
        fixed = ""
        notfixed = num
        starti = 0
        while k >= 0 and len(notfixed):
            # 不能使用starti进行跟踪，因为当前的i距离太远，不代表以后仍然太远
            # for i in range(starti, 10):
            for i in range(0, 10):  
                # print(i, k, notfixed)
                if str(i) not in notfixed:  # 各种O(N)..
                    continue
                
                idx = notfixed.index(str(i))
                if idx <= k:
                    fixed += str(i)
                    notfixed = notfixed[:idx] + notfixed[idx + 1: ]
                    k -= idx
                    starti = i  # 有可能还有相同的数字
                    break
        return fixed + notfixed

执行用时：628 ms, 在所有 Python 提交中击败了100.00%的用户
内存消耗：13.3 MB, 在所有 Python 提交中击败了100.00%的用户

First Try

2020-07-05

leetcode字节跳动周赛的题目，都没有时间做到这一题。最直接的想法就是贪心算法，跟冒泡算法一个写法。这么看起来一点都不难，问题是一直超时。结果看了题解，说是添加个判断，如果k大于nums最大需要排序的次数，直接返回nums的排序结果即可。结果竟然真的通过了。。。

但是也有一堆人说要使用线段树之类，抱歉，没听过。看起来有点复杂，一时半会也不想去了解了。所以如果最开始这个判断没有加上去，根本不知道暴力法也能够通过。

class Solution(object):
    def minInteger(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        # 01234x,对于x需要跳到第一位，只需要跳动其idx即可，也即5。
        # 如果第一位就是最小的，刚好跳动idx=0，没有问题。

        # 加了这个竟然就不超时了，我去。。
        # 最多次更换次数应该是(1+n)*n/2, 写成n^2对于测试用例也没问题
        if k >= (1 + len(num)) * len(num) / 2:
            return ''.join(sorted(num))
        fixed = ""
        notfixed = num
        while k > 0 and len(notfixed):
            minv, idx = notfixed[0], 0
            for i, v in enumerate(notfixed[:k+1]): # 第k+1位，只需要k次跳动则可到第一位
                if v < minv:
                    minv, idx = v, i
            fixed += minv
            k -= idx  # 如果idx刚好是第一位，刚好都不用消耗
            notfixed = notfixed[:idx] + notfixed[idx+1:]
        return fixed + notfixed

执行用时：2176 ms, 在所有 Python 提交中击败了100.00%的用户
内存消耗：13.2 MB, 在所有 Python 提交中击败了100.00%的用户

Time Exceeded Version

一开始写超时的版本，而且由于不知道跳动次数直接用idx就可以，导致花了许多时间判断如果第一个元素就是最小的元素，该如何处理之类，越写越乱。

事实证明，如果写得越来越乱，一般都是没有找到正确的思考方式。

   
class Solution:
    def minInteger(self, num: str, k: int) -> str:
        fixed = ""
        notfixed = num
        while k > 0 and len(notfixed):
            # print("start", k, fixed, notfixed)
            # 打补丁啊，k=1的时候就得考虑是不是要换后面的了
            if k == 1 and len(notfixed) >= 2:
                if notfixed[0] > notfixed[1]:
                    fixed += notfixed[1]
                    fixed += notfixed[0]
                    notfixed = notfixed[2:]
                    break
                else:
                    fixed += notfixed[0]
                    notfixed = notfixed[1:]
            else:
                # 在这一步超时了。。
                minv = min(notfixed[:k+1])  # 第k个元素换到1位需要k-1次，因此k次机会可以在k+1个元素中挑。之前写成了[:k]
                if minv == notfixed[0]:  # 不需要更换的
                    fixed += minv
                    notfixed = notfixed[1:]
                else:
                    idx = notfixed.index(minv)
                    k -= idx
                    fixed += minv
                    notfixed = notfixed[0:idx] + notfixed[idx+1:]
            # print("end", k, fixed, notfixed)
        return int(fixed + notfixed)