<p>你的解决方案包括26个线性扫描的字符串和一堆不必要的
计算频率的转换。通过使用线性计数步骤替换所有线性扫描、另一个线性重复生成、排序以对字母进行排序以及最后的线性传递以进行条带计数,可以节省一些工作:</p>
<pre><code>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))
</code></pre>
<hr/>
<p><strong>更新:</strong>我突然想到,我原来的解决方案可以变得更加简洁,实际上是一行程序(不包括所需的导入),它最小化了临时性,而支持单一的按键排序操作,该操作使用一种技巧,按到目前为止看到的每个字母的计数对每个字母进行排序:</p>
<pre><code>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)))
</code></pre>
<p>这实际上是与原始答案相同的基本逻辑,它只是通过让<code>sorted</code>隐式地执行值的修饰和取消修饰来完成,而不是自己显式地执行(隐式修饰/取消修饰是<code>sorted</code>的<code>key</code>参数的全部要点;它为您执行<a href="https://en.wikipedia.org/wiki/Schwartzian_transform" rel="nofollow">Schwartzian transform</a>)。你知道吗</p>
<p>就性能而言,这两种方法都是相似的;它们(在实践中)对于较小的输入都是线性扩展的(一个线性扩展到大约150个字符长的输入,较长的代码,使用<code>Counter</code>,最大扩展到<code>len</code>2000范围内的输入),虽然在这一点上增长是超线性的,但它总是低于理论<code>O(n log_2 n)</code>(可能是由于由于计数和有限的字母表,数据不是完全随机的,因此确保Python的TimSort有一些现有的顺序可以利用)。对于较小的字符串(<code>len</code>100或更少),一行代码的速度要快一些,对于较大的字符串,较长的代码的速度要快一些(我猜这与较长的代码通过对每个字母的计数运行进行分组来创建一些排序有关)。实际上,除非输入字符串是巨大的,否则这并不重要。你知道吗</p>