根据字符出现频率排序

原文记录了两条思路。这里把题意与思路一的实现原理写完整，代码保留原样。

题目背景

LeetCode 451「根据字符出现频率排序」。给定一个字符串 s，要求按字符出现频率从高到低返回新字符串；频率相同的字符相对位置不强制要求。

概念解释

频率统计：经典的”哈希表/数组计数”模式。Key 是字符，Value 是它出现的次数。
大顶堆 / 优先队列：要按”次数从大到小”输出，可以把 (char, count) 对入堆，top() 给出最高频字符。
map::value_comp：std::map 的比较器只作用于 key，不能直接按 value 排序，因此原文思路二行不通。

实现原理

思路一（被采用）：

用 std::map<char,int> 遍历 s，统计每个字符出现的次数。
把所有 (char, count) 入大顶堆 priority_queue，比较器返回 p1.second < p2.second，让 top() 拿到最高频。
反复弹出堆顶，把对应字符按 count 重复追加到结果字符串里，直至堆空。

时间复杂度 O(n + k log k)：n 为字符串长度，k = O(unique chars)，最坏 k ≤ 128；空间复杂度 O(k + n)（堆 + 输出字符串）。

备注：思路二想直接用 map::value_comp 按 value 排序失败，原因如上：map 的比较器只针对 key。如果想”少写一个堆”，可以改用 vector<pair<char,int>> 配 std::sort 自定义比较器。

参考实现

思路一: 先用map 记录次数，然后使用 优先队列按照频率进行排序

思路二: 开始考虑直接使用map 内置的 value_comp，没有成功！！！！！

class Solution {
public:
    string frequencySort(string s) {

        std::map<char,int> mp;

        auto cmp = [](std::pair<char,int> p1, std::pair<char,int> p2){
            return p1.second < p2.second;
        };
        std::priority_queue<std::pair<char,int>, std::vector<std::pair<char,int> >,decltype(cmp)> pq(cmp);


        for_each(s.begin(),s.end(),[&](auto item){
            mp[item]++;
        });

        auto iter = mp.begin();

        while(iter != mp.end())
        {
            pq.emplace(std::make_pair(iter->first,iter->second));
            ++iter;
        }
        std::string ret;
        while(!pq.empty())
        {
            auto t = pq.top();
            // std::cout << t.first << " " << t.second << std::endl;
            auto count = t.second;
            while(count > 0)
            {
                ret += t.first;
                --count;
            }
            pq.pop();
        }

        return ret;

    }
};

FEATURED TAGS

Git Cheat Sheet Markdown Tools C++ Linker Thread Linux TCP Network GDB Debug leetcode 链表 WSL Ubuntu Windows Linux Kernel GCC Android adb Troubleshooting Profiling Sanitizer glibc MySQL Database Python curl Build ELF clang-format CMake Graphviz Performance vcpkg Protobuf 排查速查内存 STL 调试性能分析性能读书笔记方法论架构网络 Timer mbedTLS TLS 安全负载均衡脚本工具 LRU 二叉树 BST 中序遍历回溯二分查找优先队列排序旋转数组 jenkins 部署

LeetCode 451 题解笔记

CATALOG

题目背景

概念解释

实现原理

参考实现

FEATURED TAGS

FRIENDS