用 Python 编写程序，在最多 k 次相邻数字交换后找到最小可能整数

pythonserver side programmingprogramming更新于 2025/11/30 23:08:17

假设我们有一个名为 num 的字符串，表示一个非常大的整数，并且还有另一个值 k。我们可以最多 k 次交换任意两个相邻的数字。我们必须找到可以得到的最小值。

因此，如果输入像 num = "5432" k = 4，则输出将为 2453，因为第一个数字是 5432。然后经过第一阶段后，它将是 4532，然后是 4523，然后是 4253，最后阶段是 2453。

为了解决这个问题，我们将遵循以下步骤

min_num := 对 num 的数字进行排序
i := 0, to_find := 0
当 num 与 min_num 不同且 k > 0 且 i < num 的大小，执行
- indx := num 中从索引 i 开始的 to_find 项的索引
- 当 indx 不等于 -1 时，执行
  - 如果 indx - i <= k，则
    - num := num[从索引 0 到 i-1] 连接 num[indx] 连接 num[从索引 i 到 indx-1] 连接 num[从索引 indx+1 到结束]
    - k := k -(indx - i)
    - i := i + 1
    - to_find := 0
    - indx := num 中索引 i 中 to_find 项的索引
  - 否则，
    - 退出循环
- to_find := to_find + 1
返回 num

示例

让我们看看下面的实现以便更好地理解

def solve(num, k):
   min_num = sorted(list(num))
   min_num = ''.join(min_num)
   i = 0
   to_find = 0
   while num != min_num and k > 0 and i < len(num):
      indx = num.find(str(to_find), i)
      while indx != -1:
         if indx - i <= k:
            num = num[:i] + num[indx] + num[i:indx] + num[indx+1:]
            k -= (indx - i)
            i += 1
            to_find = 0
            indx = num.find(str(to_find), i)
         else:
            break
      to_find += 1
   return num

num = "5432"
k = 4
print(solve(num, k))