【LeetCode451】根据字符出现频率排序(优先队列)

简介: 【LeetCode451】根据字符出现频率排序(优先队列)(1)根据词频排序,很容易想到用哈希表统计每个字符的个数,然后排序。对于“求前k个”或“排序”的题目可以使用堆排序,用优先级队列实现最大堆,进行堆排序,堆顶即当前的最大值。因为我们的pair<char, int>的second才是对应字符(first)的词频,需要的是对second进行排序,所以重写cmp。

一、题目

image.pngimage.png



二、思路

(1)根据词频排序,很容易想到用哈希表统计每个字符的个数,然后排序。对于“求前k个”或“排序”的题目可以使用堆排序,用优先级队列实现最大堆,进行堆排序,堆顶即当前的最大值。因为我们的pair<char, int>的second才是对应字符(first)的词频,需要的是对second进行排序,所以重写cmp。


(2)string(num, c)是生成一个包含num个c字符的字符串,这题试了用for循环实现竟然会超时。


(3)其实vector就能够排序了,不用priority_queue也是可以的。


【C++中STL的优先级队列】

在C++的stl中有priority_queue优先级队列,其具体参数如下:

priority_queue<Type, Container, Functional>:


Type 就是数据类型,

Container 就是容器类型(Container必须是用数组实现的容器,比如vector,deque等等,但不能用 list。STL里面默认用的是vector)

Functional 就是比较的方式。

PS:当需要用自定义的数据类型时才需要传入这三个参数,使用基本数据类型时,只需要传入数据类型,默认是大顶堆。


cmp:大的优先级在前面,注意:堆的优先级的返回值与排序的正好相反。


三、代码

class Solution {
struct cmp{
    bool operator()(pair<char, int>&a, pair<char, int>&b){
        return a.second < b.second;
        //大的优先级在前面,注意:堆的优先级的返回值与排序的正好相反
    }
};
public:
    using stu = pair<char, int>; 
    string frequencySort(string s) {
        unordered_map<char, int>mp(26);
        for(int i = 0; i < s.size(); i++){
            mp[s[i]]++;
        }
        priority_queue<stu, vector<stu>, cmp>pq;
        for(auto &[key, value]: mp){
            //每一个pair
            pq.push({key, value});
        }
        string ans = "";
        while(!pq.empty()){
            auto [c, num] = pq.top();
            pq.pop();
            ans = ans + string(num, c);
        }
        return ans;
    }
};

image.png

相关文章
|
4天前
|
存储 算法 程序员
【Leetcode 程序员面试金典 01.01】判定字符是否唯一 —— 位运算|哈希表
可以使用哈希表或位运算来解决此问题:由题可知s[i]仅包含小写字母,int[26]即能表示字符的出现次数;
|
4天前
|
网络协议
《 LeetCode 热题 HOT 100》——无重复字符的最长子串
《 LeetCode 热题 HOT 100》——无重复字符的最长子串
|
4天前
|
存储 JavaScript
leetcode82. 删除排序链表中的重复元素 II
leetcode82. 删除排序链表中的重复元素 II
25 0
|
4天前
leetcode83. 删除排序链表中的重复元素
leetcode83. 删除排序链表中的重复元素
12 0
|
4天前
|
索引
力扣1859 将句子排序
力扣1859 将句子排序
|
4天前
|
存储 算法 Go
LeetCode 第三题: 无重复字符的最长子串
  给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。
|
4天前
【Leetcode 2583】二叉树中的第K大层和 —— 优先队列 + BFS
解题思路: - 使用队列保存节点,按层序依次保存该层节点 - 使用优先队列保存每层节点值的总和,最后剔除前k个大数即可得到
|
4天前
|
算法 C++
【刷题】Leetcode 1609.奇偶树
这道题是我目前做过最难的题,虽然没有一遍做出来,但是参考大佬的代码,慢慢啃的感觉的真的很好。刷题继续!!!!!!
9 0
|
4天前
|
算法 索引
【刷题】滑动窗口精通 — Leetcode 30. 串联所有单词的子串 | Leetcode 76. 最小覆盖子串
经过这两道题目的书写,相信大家一定深刻认识到了滑动窗口的使用方法!!! 下面请大家继续刷题吧!!!
12 0