每日一道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()])