python - 找到排序字符串所需的最小字母交换量

Question

我有一个问题，我需要找到对字符串进行排序所需的最少字母交换量。每次移动，我都可以交换两个字符的位置（不一定相邻），我需要找到最小的交换量。

我以前用二进制解决了一个类似的问题（需要位交换相邻）。所以排序101010 => 000111会返回6，但找不到一种方法来概括我的解决方案：

def sort(s):
    ones = 0
    res = 0
    for b in s:
        if b == "1":
            ones += 1
        if b == "0":
            res += ones
    return res

我应该ord()以某种方式在此处合并该函数以改变问题以处理整数吗？任何提示将不胜感激。

标签： pythonsorting

Answer 1

最小交换次数由字母所在排列的循环分解确定，相对于排序顺序。例如，假设单词是，那么排序顺序是，循环是"wonderful""deflnoruw"

• w → d, d → l,l → w
• o → e, e → n, n → f, f → r,r → o
• u → u

循环的长度分别为 3、5 和 1，因此我们从每个长度中减去 1 以获得执行这些循环所需的最小交换次数：2 + 4 + 0 = 6 次交换。等效地，交换次数是字符串长度减去循环次数：9 - 3 = 6。

所以，你的算法需要按照这个想法工作；它可能有助于研究循环排序算法，该算法找到实际进行排序的循环。另请注意，当单词有重复字母时，它比上面的示例要复杂一些。