每日一道Leetcode - 451. 根据字符出现频率排序【大顶堆｜桶排序】

方法一：大顶堆

注意存储的时候将频次存为负数，正常是小顶堆

class Solution:
    def frequencySort(self, s: str) -> str:
        # 大顶堆
        # 计算每个出现的频次
        countFrequency = collections.defaultdict(int)
        for i in s:
            countFrequency[i] += 1
        queue = []
        heapq.heapify(queue)
        for i in countFrequency:
            heapq.heappush(queue,(-countFrequency[i],i))
        res = []
        for _ in range(len(countFrequency)):
            a = heapq.heappop(queue)
            res.extend(a[1]*(-a[0]))
        return ''.join(res)
           

方法二：桶排序

class Solution:
    def frequencySort(self, s: str) -> str:
        # 桶排序
        # 计算每个出现的频次
        countFrequency = collections.defaultdict(int)
        for i in s:
            countFrequency[i] += 1
        
        # 为每个频次准备一个桶，可能出现所有不同的频次
        buckets = [[] for _ in range(len(s)+1)]

        for i in countFrequency:
            buckets[countFrequency[i]].extend(i*countFrequency[i])
        
        res = []

        # 倒序
        for i in buckets[::-1]:
            if i:
                res.extend(i)

        return ''.join(res)

           

方法三：直接调用库函数

class Solution:
    def frequencySort(self, s: str) -> str:
        return ''.join([i*j for i,j in collections.Counter(s).most_common()])