1.题目基本信息

1.1.题目描述

给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。

返回 已排序的字符串 。如果有多个答案，返回其中任何一个。

1.2.题目地址

https://leetcode.cn/problems/sort-characters-by-frequency/description/

2.解题方法

2.1.解题思路

大根堆。统计字符频数，并压入大根堆并依次取出，再组合成新的字符串

3.解题代码

python代码

from collections import Counter
from heapq import heappush, heappop

class Solution:
    def frequencySort(self, s: str) -> str:
        # 思路：大根堆
        cnts = Counter()
        for c in s:
            cnts[c] += 1
        heap = []
        for k, v in cnts.items():
            heappush(heap, [-v, k])
        result = ""
        while heap:
            v, k = heappop(heap)
            result += k * -v
        return result

c++代码

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> cnts;
        for (char &c:s) {
            cnts[c] += 1;
        }
        vector<pair<char, int>> arr;
        for (auto &item:cnts) {
            arr.emplace_back(item);
        }
        sort(arr.begin(), arr.end(), [](const pair<char, int> &a, const pair<char, int> &b){
            return a.second > b.second;
        });
        string result;
        for (auto &[k, v]:arr) {
            for (int i = 0; i < v; i++) {
                result += k;
            }
        }
        return result;
    }
};

4.执行结果