对字符串进行排序以生成新字符串

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)

但它超过了允许的运行时间限制，可能是因为循环太多。（还有另一个 for 循环将字符串与用户输入分开）

我希望有人可以建议使用更少内存的更优化版本 space。

Answer 1

这个呢？我正在使用内置的 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 2

由于字母表始终是 26 个字符，这将在 O(N) 中工作，并且只需要 26

的恒定数量 space

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

Answer 3

您的解决方案涉及字符串的 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 隐式地执行值的修饰和取消修饰而不是我们自己显式地进行（隐式 decorate/undecorate是 sorted 的 key 论点的重点；它正在为你做 Schwartzian transform。

在性能方面，两种方法都相似；它们（在实践中）都针对较小的输入进行线性缩放（一行最多输入大约 150 个字符长，较长的代码，使用 Counter，最多输入在 len 2000 范围内），并且虽然在该点以上增长是超线性的，但它总是低于理论值 O(n log_2 n)（可能是由于计数和有限的字母表导致数据不是完全随机的，确保 Python 的 TimSort 有一些要利用的现有订单）。对于较小的字符串（len 100 或更少），单行代码稍快一些，对于较大的字符串，较长的代码稍快一些（我猜它与较长的代码有关，通过分组运行创建一些排序每个字母的计数）。不过，实际上，除非预计输入字符串很大，否则这并不重要。

对字符串进行排序以生成新字符串

Sorting a string to make a new one

python

sorting

string

nested-loops

python-2.7