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

Question

我想解决这个问题：

给定一个输入字符串，按频率递减的顺序对字符进行排序。若有多个字符具有相同的频率计数，则按字典顺序递增对其进行排序。示例：

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

我的解决方案包括在哈希映射中创建频率，使用sorted((和lambda函数按频率对哈希映射dict项进行排序。然后，对于具有相同频率的项(我需要为此编写一个子例程(，我使用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})

Answer 2

计数器&amp__lt__方法

我认为你的任务可以分为两个任务：

1. count任务，这可以通过Counter类轻松实现，但Counter不能保证其密钥的顺序，因此需要任务2
2. 排序任务(像CPP这样的比较器(，您需要一个自定义的排序函数，这样您就可以创建一个新的类并实现__lt__方法，doc

from collections import Counter
class Item:
def __init__(self, ch, times):
self.ch = ch
self.times = times
def __lt__(self, other):
if self.times > other.times:
return True
if self.times == other.times:
return self.ch < other.ch
return False
# my restruct 
def restruct(inp):
c = Counter(inp)
data = sorted([Item(ch, times) for ch, times in c.items()])
return ''.join([item.ch*item.times for item in data])

继restruct之后，@juanpa.arrivilaga提供了一个非常优雅的工具(具有同样的能力(，谢谢他。

def restruct(inp):
c = Counter(inp)
return ''.join(sorted(inp, key=lambda ch: Item(ch, c[ch])))

然后尝试restruct('bacbdc')获得bbccad，宾果！！！