451 Sort Characters By Frequency

方法一: 使用Python sort 函数 时间复杂度：O(nlogn)

方法二：使用heapq 最小堆 时间复杂度：O()

class Solution(object):
    def frequencySort(self, s):
        """
        :type s: str
        :rtype: str
        """
        d = {}
        for char in s:
            if char in d:
                d[char] += 1
            if char not in d:
                d[char] = 1
        data = []
        for key, value in d.items():
            data.append((value, key))
        data.sort(key = lambda item: item[0], reverse = True)
        ans = ""
        for i in range(len(data)):
            ans += data[i][1]*data[i][0]
        return ans

import heapq
class Solution(object):
    def frequencySort(self, s):
        """
        :type s: str
        :rtype: str
        """
        d = {}
        for char in s:
            if char in d:
                d[char] += 1
            if char not in d:
                d[char] = 1
        data = []
        for key, value in d.items():
            data.append((-value, key))
        heapq.heapify(data)
        ans = ""
        while len(data):
            (value, key) = heapq.heappop(data)
            value = -value
            for i in range(value):
                ans += key
        return ans