基于某种形式的字符串排序

Question

我有一个字符串需要根据sort_fmt排序。例如：如果字符串是'abdcdfs'&排序为'dacg'。排序时，输出应为“ddacfs”。如您所见，输入字符串中可能存在顺序字符串中没有的字符，反之亦然。顺序字符串中不存在的输入字符串字符应以任何顺序出现在输出字符串的末尾。在

这是我写的。它有效，是O（n*m）算法。我想知道有没有更好和更短的方法来实现这一点？可能使用itertools？在

def sort_str(s, sort_fmt):
    sorted_str = ''
    str_hash   = dict()

    # O(n)
    for ch in s:
        if ch in str_hash:
            str_hash[ch] += 1
        else:
            str_hash[ch] = 1

    # O(m) + O(1) where m<=n
    for ch in sort_fmt:
        if ch in str_hash:
            cnt = str_hash[ch]
            sorted_str += cnt * ch

    # O(n)
    for ch in s:
        if ch not in sort_fmt:
            sorted_str += ch
    return sorted_str


if __name__ == '__main__':
    print sort_str('abdcdfs', 'dacg')

Answer 1

您正在尝试实现counting sort，它在某些条件下确实是O（n）。但是，您的实现在接近尾声时有两个错误，这意味着您的实现的实际时间复杂性是O（n²+n*m）：

for ch in s:
    if ch not in sort_fmt:  # < - "in" requires a linear search. O(n*m)
        sorted_str += ch    # < - Ouch! Concatenation! O(n^2)

• 因为在循环中使用串联，所以构造结果的方式效率很低。在
• 在字符串上使用in在字符串长度上是线性的，您是在一个循环中这样做的。在

试试这个。由于使用了collections.Counter，它需要python2.7或更高版本，但是对于旧版本的Python，Counter可以很容易地替换为defaultdict）：

^{pr2}$

如果您放弃了应该是O（n）的要求，这里有一个更简洁的方法来获得您想要的结果：

>>> d = dict((v,k) for (k,v) in enumerate('dacg'))
>>> sorted('abdcdfs', key = lambda c:d.get(c, len(d)))
['d', 'd', 'a', 'c', 'b', 'f', 's']

Answer 2

我不确定排序的复杂性。这很管用

def sort_str(s, frmt):
    l = len(frmt)
    return sorted(s, key = lambda x: frmt.index(x) if x in frmt else l)