MENU

LeetCode451. Sort Characters By Frequency(模拟)

2019 年 02 月 15 日・阅读: 1446・LeetCode阅读设置

LeetCode451. Sort Characters By Frequency(模拟)

  • Medium
  • Accepted:81,281
  • Submissions:148,685

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.

链接

https://leetcode.com/problems/sort-characters-by-frequency/

题意

给定一个字符串,按照字符出现的频率从大到到小排序。相同字符相邻,频率相同时不同字符顺序可以不同,区分大小写。

题解

  • 对字符按照出现次数用 sort 进行排序,时间复杂度 $O (nlogn)$
  • 对字符进行 “计数排序”,灵活使用 vector,将出现次数相同的字符放到一起,再从后往前遍历

代码

  • Runtime: 48 ms, faster than 30.00% of C++ online submissions for Sort Characters By Frequency.
  • Memory Usage: 10.5 MB, less than 100.00% of C++ online submissions for Sort Characters By Frequency.
  • 话说直接写 cmp 函数会报错(已发现错误:reference to non-static member function must be called
  • class Solution {
  • public:
  • // int cnt[256] = {0};
  • //
  • // bool cmp(char a, char b)
  • // {
  • // return cnt[a] > cnt[b] || (cnt[a] == cnt[b] && a < b);
  • // }
  • string frequencySort(string s) {
  • int n = s.length();
  • int cnt[256] = {0};
  • for (int i = 0; i < n; ++i)
  • cnt[s[i]]++;
  • // sort(s.begin(), s.end(), cmp); // error
  • sort(s.begin(), s.end(), [&](char a, char b) // 高级写法
  • {
  • return cnt[a] > cnt[b] || (cnt[a] == cnt[b] && a < b);
  • });
  • return s;
  • }
  • };
  • Runtime: 28 ms, faster than 42.31% of C++ online submissions for Sort Characters By Frequency.
  • Memory Usage: 18.6 MB, less than 100.00% of C++ online submissions for Sort Characters By Frequency.
  • class Solution {
  • public:
  • string frequencySort(string s) {
  • int n = s.length();
  • unordered_map <char, int> umap;
  • vector <string> vt(n + 1, "");
  • string ans;
  • for (int i = 0; i < n; ++i) // 统计字符出现次数
  • umap[s[i]]++;
  • unordered_map <char, int> ::iterator it;
  • for (it = umap.begin(); it != umap.end(); ++it) // 次数相同的放到一起
  • vt[it->second].append(it->second, it->first);
  • for (int i = n; i > 0; --i) // 从后往前遍历
  • {
  • if (!vt[i].empty())
  • ans.append(vt[i]);
  • }
  • return ans;
  • }
  • };

The end.
2019 年 2 月 15 日 星期五
最后编辑于: 2019 年 02 月 17 日