{"id":30,"date":"2017-03-18T13:02:35","date_gmt":"2017-03-18T20:02:35","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=30"},"modified":"2018-04-19T08:43:33","modified_gmt":"2018-04-19T15:43:33","slug":"leetcode-451-sort-characters-by-frequency","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/leetcode\/leetcode-451-sort-characters-by-frequency\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 451. Sort Characters By Frequency"},"content":{"rendered":"

Given a string, sort it in decreasing order based on the frequency of characters.<\/p>\n

Example 1:<\/b><\/p>\n

Input:<\/b>\r\n\"tree\"\r\n\r\nOutput:<\/b>\r\n\"eert\"\r\n\r\nExplanation:<\/b>\r\n'e' appears twice while 'r' and 't' both appear once.\r\nSo 'e' must appear before both 'r' and 't'. Therefore \"eetr\" is also a valid answer.\r\n<\/pre>\n
Example 2:<\/b><\/p>\n
<b>Input:<\/b>\r\n\"cccaaa\"\r\n\r\n<b>Output:<\/b>\r\n\"cccaaa\"\r\n\r\n<b>Explanation:<\/b>\r\nBoth 'c' and 'a' appear three times, so \"aaaccc\" is also a valid answer.\r\nNote that \"cacaca\" is incorrect, as the same characters must be together.\r\n<\/pre>\n
Example 3:<\/b><\/p>\n
<b>Input:<\/b>\r\n\"Aabb\"\r\n\r\n<b>Output:<\/b>\r\n\"bbAa\"\r\n\r\n<b>Explanation:<\/b>\r\n\"bbaA\" is also a valid answer, but \"Aabb\" is incorrect.\r\nNote that 'A' and 'a' are treated as two different characters.\r\n<\/pre>\n
<\/div>\n
Solution:<\/strong><\/div>\n
\n
class Solution {\r\npublic:\r\n    string frequencySort(string s) {\r\n        map<char, int> f;\r\n        for(char c:s) ++f[c];\r\n        vector<pair<int,char>> v;\r\n        for(auto& kv : f)\r\n            v.push_back({kv.second, kv.first});\r\n        sort(v.rbegin(), v.rend());\r\n        stringstream ans;\r\n        for(auto& kv : v)\r\n            ans << string(kv.first, kv.second);\r\n        return ans.str();\r\n    }\r\n};<\/pre>\n
 <\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[24,23,4],"class_list":["post-30","post","type-post","status-publish","format-standard","hentry","category-leetcode","tag-frequency","tag-sort","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/30","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=30"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/30\/revisions"}],"predecessor-version":[{"id":2735,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/30\/revisions\/2735"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=30"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=30"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=30"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}