String基于某些格式排序

Question

我有一个字符串需要根据sort_fmt.例如:如果字符串是'abdcdfs'并且sort_fmt是'dacg'.排序后,输出应为'ddacfbs'.如您所见,输入字符串中可能存在字符串中不存在的字符,反之亦然.输入字符串中不存在于订单字符串中的字符应以任何顺序出现在输出字符串的末尾.

这是我写的.它有效,它是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

您正在尝试实现计数排序,在某些条件下确实是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一个字符串是在字符串的长度线性的,你是在一个循环中这样做.

试试这个.它需要Python 2.7或更新版本,因为它的使用collections.Counter,但Counter可以很容易地用defaultdict旧版本的Python 替换):

from collections import Counter

def sort_str(s, sort_fmt):
    counter = Counter(s)
    d = set(sort_fmt)
    result = ''.join(c * counter[c] for c in sort_fmt)
    result += ''.join(c for c in s if c not in d)
    return result

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

如果你放弃它应该是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']