python - 按字符频率对字符串进行排序，按字母顺序打破联系

Question

我想解决这个问题:

给定一个输入字符串，按频率降序对字符进行排序。如果多个字符具有相同的频率计数，则按字典顺序递增对它们进行排序。示例:

bdca --> abcd,
bdcda -> ddabc,
abba -> aabb,
bacbdc -> bbccad,

我的解决方案涉及在 HashMap 中创建频率，使用sorted()和lambda函数按频率对 HashMap 字典项进行排序。然后，对于具有相同频率的项目(我需要为此编写一个子例程)，我使用 lambda 函数进行另一个排序。

def string_sort(s):
    hmap = {}
    for char in s:
        if char not in hmap:
            hmap[char] = 1
        else:
            hmap[char] += 1
    freqs = sorted(hmap.items(), key=lambda x: x[1], reverse=True)
    num_occur: list = find_num_occur(freqs)
    sorted_freqs = []
    start_ind = 0
    for f in num_occur:
        tmp_freqs = sorted(freqs[start_ind : start_ind + f], key=lambda x: x[0])
        sorted_freqs.extend(tmp_freqs)
        start_ind = len(sorted_freqs)
    out = []
    for item in sorted_freqs:
        out.extend([item[0]] * item[1])
    return "".join(out)


def find_num_occur(freqs):
    count = 1
    out = []
    for i in range(len(freqs) - 1):
        if freqs[i][1] == freqs[i + 1][1]:
            count += 1
        else:
            out.append(count)
            count = 1
    out.append(count)
    return out

解决方案并不优雅。有人告诉我如果使用比较器可以更容易地解决这个问题，但我不知道如何在 python 中使用比较器。有什么建议么？或者任何其他更优雅的解决方案？

谢谢。

Answer 1

您不需要使用比较器，您可以使用按键功能就可以了。您的解决方案中有很多不必要的复杂性，您所需要的只是达到以下效果:

>>> from collections import Counter
>>> def transmogrify(s):
...     counts = Counter(s)
...     return ''.join(sorted(s, key=lambda c: (-counts[c], c)))
...
>>> transmogrify('bdca')
'abcd'
>>> transmogrify('bdcda')
'ddabc'
>>> transmogrify('abba')
'aabb'
>>> transmogrify('bacbdc')
'bbccad'

请注意，collections.Counter 只是一个专门用于计数的dict，因为它是一种足够常见的模式。

>>> Counter('bacbdc')
Counter({'b': 2, 'c': 2, 'a': 1, 'd': 1})