对字符串排序以生成新的

Question

在这里，我必须删除字符串中最频繁的字母表（如果两个字母表的频率相同，则按字母顺序排列），然后将其放入新字符串中。你知道吗

输入：

abbcccdddd

输出：

dcdbcdabcd

我写的代码是：

s = list(sorted(<the input string>))
a = []
for c in range(len(s)):
    freq =[0 for _ in range(26)]
    for x in s:
        freq[ord(x)-ord('a')] += 1
    m = max(freq)
    allindices = [p for p,q in enumerate(freq) if q == m]
    r = chr(97+allindices[0])
    a.append(r)
    s.remove(r)
print''.join(a)

但它超过了允许的运行时限制，可能是因为循环太多了

我希望有人能推荐一个更优化的版本，使用更少的内存空间。你知道吗

Answer 1

你的解决方案包括26个线性扫描的字符串和一堆不必要的 计算频率的转换。通过使用线性计数步骤替换所有线性扫描、另一个线性重复生成、排序以对字母进行排序以及最后的线性传递以进行条带计数，可以节省一些工作：

from collections import Counter      # For unsorted input
from itertools import groupby        # For already sorted input
from operator import itemgetter

def makenewstring(inp):
    # When inp not guaranteed to be sorted:
    counts = Counter(inp).iteritems()

    # Alternative if inp is guaranteed to be sorted:
    counts = ((let, len(list(g))) for let, g in groupby(inp))

    # Create appropriate number of repetitions of each letter tagged with a count
    # and sort to put each repetition of a letter in correct order
    # Use negative n's so much more common letters appear repeatedly at start, not end
    repeats = sorted((n, let) for let, cnt in counts for n in range(0, -cnt, -1))

    # Remove counts and join letters
    return ''.join(map(itemgetter(1), repeats))

---

更新：我突然想到，我原来的解决方案可以变得更加简洁，实际上是一行程序（不包括所需的导入），它最小化了临时性，而支持单一的按键排序操作，该操作使用一种技巧，按到目前为止看到的每个字母的计数对每个字母进行排序：

from collections import defaultdict
from itertools import count

def makenewstring(inp):
    return ''.join(sorted(inp, key=lambda c, d=defaultdict(count): (-next(d[c]), c)))

这实际上是与原始答案相同的基本逻辑，它只是通过让sorted隐式地执行值的修饰和取消修饰来完成，而不是自己显式地执行（隐式修饰/取消修饰是sorted的key参数的全部要点；它为您执行Schwartzian transform）。你知道吗

就性能而言，这两种方法都是相似的；它们（在实践中）对于较小的输入都是线性扩展的（一个线性扩展到大约150个字符长的输入，较长的代码，使用Counter，最大扩展到len2000范围内的输入），虽然在这一点上增长是超线性的，但它总是低于理论O(n log_2 n)（可能是由于由于计数和有限的字母表，数据不是完全随机的，因此确保Python的TimSort有一些现有的顺序可以利用）。对于较小的字符串（len100或更少），一行代码的速度要快一些，对于较大的字符串，较长的代码的速度要快一些（我猜这与较长的代码通过对每个字母的计数运行进行分组来创建一些排序有关）。实际上，除非输入字符串是巨大的，否则这并不重要。你知道吗

Answer 2

这个怎么样？ 我正在使用内置的python函数来消除循环并提高效率。你知道吗

test_str = 'abbcccdddd'

remaining_letters = [1]   # dummy initialisation
# sort alphabetically
unique_letters = sorted(set(test_str))
frequencies = [test_str.count(letter) for letter in unique_letters]

out = []

while(remaining_letters):

    # in case of ties, index takes the first occurence, so the alphabetical order is preserved  
    max_idx = frequencies.index(max(frequencies))    
    out.append(unique_letters[max_idx])

    #directly update frequencies instead of calculating them again
    frequencies[max_idx] -= 1  
    remaining_letters = [idx for idx, freq in enumerate(frequencies) if freq>0]

print''.join(out)   #dcdbcdabcd

Answer 3

因为字母表总是固定的26个字符， 这将在O（N）中工作，并且只需要26的常量空间

from collections import Counter
from string import ascii_lowercase

def sorted_alphabet(text):
    freq = Counter(text)
    alphabet = filter(freq.get, ascii_lowercase) # alphabet filtered with freq >= 1
    top_freq = max(freq.values()) if text else 0 # handle empty text eg. ''
    for top_freq in range(top_freq, 0, -1): # from top_freq to 1
        for letter in alphabet:
            if freq[letter] >= top_freq:
                yield letter

print ''.join(sorted_alphabet('abbcccdddd'))
print ''.join(sorted_alphabet('dbdd'))
print ''.join(sorted_alphabet(''))
print ''.join(sorted_alphabet('xxxxaaax'))

---

dcdbcdabcd
ddbd

xxaxaxax