【leetcode451】根據字元出現頻率排序，雜湊表加優先佇列解法

題文

給定一個字串，請將字串裡的字元按照出現的頻率降序排列。

樣例

樣例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（nlogn）$
空間複雜度：一般情況下為$O（logn）$，最差情況下為$O（n）$