String根据某种格式排序

我有一个字符串需要根据sort_fmt排序。例如：如果字符串是'abdcdfs'& sort_fmt是'dacg'。排序后，输出应该是'ddacfbs'。如您所见，输入字符串中可能存在不存在于订单字符串中的字符，反之亦然。输入字符串中没有出现在命令字符串中的字符应以任何顺序出现在输出字符串的末尾。String根据某种格式排序

这是我写的。它的工作原理是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')

来源

2010-12-19 Srikar Appalaraju

O（n）sort？你确定吗？ – 2010-12-19 10:15:57

您试图实施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在字符串的长度上是线性的，并且您在循环中执行此操作。

试试这个。它需要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']

来源

2010-12-19 10:15:56

第二个字典的任何理由？它应该与元组一起工作吗？ d = dict（（v，k）代表k，v代表枚举（'dacg'）） – 2010-12-19 10:25:39

@彼得吉布森：不，没有理由，那只是一个错字。 :)修正，谢谢。 – 2010-12-19 10:28:05

所以最好的可以做的是O（n * m）？ – 2010-12-19 10:32:41

我不确定排序的复杂性。 This works

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

来源

2010-12-19 10:23:00 dheerosaur

String根据某种格式排序

回答

相关问题