【leetcode451】根据字符出现频率排序，哈希表加优先队列解法

男娘i 2022-12-14 15:56 158阅读 0赞

## 题文 ##

> 给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

## 样例 ##

样例1

> 输入: “tree”
> 
> 输出: “eert”
> 
> 解释: 'e’出现两次，'r’和’t’都只出现一次。 因此’e’必须出现在’r’和’t’之前。此外，"eetr"也是一个有效的答案。

样例2

> 输入: “cccaaa”
> 
> 输出: “cccaaa”
> 
> 解释: 'c’和’a’都出现三次。此外，"aaaccc"也是有效的答案。 注意"cacaca"是不正确的，因为相同的字母必须放在一起。

样例3

> 输入: “Aabb”
> 
> 输出: “bbAa”
> 
> 解释: 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。 注意’A’和’a’被认为是两种不同的字符。

## 思路： ##

遍历一遍字符串，用哈希表记录每个字符出现的频率；  
构建结构体，成员为哈希表的迭代器，定义优先级  
创建结构体的优先队列  
遍历一遍哈希表，将迭代器作为构造参数创建匿名结构体（有匿名对象这种说法，但不知道有没有匿名结构体这种说法），加入到优先队列中。  
遍历队列，每次将队列中出现次数最多的字符追加到我们需要返回的答案字符串中。

## 代码实现 ##

class Solution {
    public:
        struct status{
            unordered_map<char,int> ::iterator it;
            bool operator <(const status& p) const{
                return it->second<p.it->second;
            }
        };
        priority_queue <status>q;
        string frequencySort(string& s) {
            string ans;
            unordered_map<char,int> hashmap;
            for(char&ch:s) ++hashmap[ch];
            for(unordered_map<char,int>::iterator it=hashmap.begin();it!=hashmap.end();++it)
                q.push(status{it});
            while(!q.empty()){
                auto it=q.top().it;
                q.pop();
                ans.append(it->second,it->first);
            }
            return ans;
        }
    };

## 算法分析 ##

时间复杂度：最差情况下为 O （ n l o g n ） O（nlogn） O（nlogn）  
空间复杂度：一般情况下为 O （ l o g n ） O（logn） O（logn），最差情况下为 O （ n ） O（n） O（n）