LeetCode 451. Sort Characters By Frequency

今天因為要寫作業，全英回答，寫完作業就去看了英雄聯盟直播，看到WE贏了！！花費了很多時間，所以沒有做幾道題，所以文章也發的比較晚。

進入今天的正題：

Description :

Given a string, sort it in decreasing(降序) order based on the frequency(頻率) of characters.

Example 1:

Input:"tree"Output:"eert"Explanation:e appears twice while r and t both appear once.So e must appear before both r and t. Therefore "eetr" is also a valid answer.

Example 2:

Input:"cccaaa"Output:"cccaaa"Explanation:Both c and a appear three times, so "aaaccc" is also a valid answer.Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:"Aabb"Output:"bbAa"Explanation:"bbaA" is also a valid answer, but "Aabb" is incorrect.Note that A and a are treated as two different characters.

這道題還是比較有意思的，首先應該想到的是運用字元的ASCII值去建立數組求解，而不是簡單判斷是否兩個字元是否相等！

解題代碼：

version 1 ：

class Solution {public: string frequencySort(string s) { unordered_map<char,int> freq; vector<string> bucket(s.size()+1, ""); string res; //count frequency of each character for(char c:s) freq[c]++; //put character into frequency bucket for(auto& it:freq) { int n = it.second; char c = it.first; bucket[n].append(n, c); } //form descending sorted string for(int i=s.size(); i>0; i--) { if(!bucket[i].empty()) res.append(bucket[i]); } return res; }};

version 2 ：

class Solution {public: string frequencySort(string s) { int counts[256] = {0}; for (char ch : s) ++counts[ch]; sort(s.begin(), s.end(), [&](char a, char b) { return counts[a] > counts[b] || (counts[a] == counts[b] && a < b); }); return s; }};

希望大家關注一下我，我會每天都發一篇文章來感謝大家，也歡迎關注我的微信公眾號，鏈接在文末，也可以直接搜索微信號liss_H。大家記得點贊再走！歡迎留言和提建議，謝謝。

http://weixin.qq.com/r/oTg9JR3EIEBfrVlG922z (二維碼自動識別)

推薦閱讀：