題文
給定一個字串，請將字串里的字符按照出現的頻率降序排列，
樣例
樣例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）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/172464.html
標籤：其他
上一篇：Unity（一）入門：Unity Hub下載 Unity安裝
下一篇：遞回-迷宮問題和八皇后問題