LeetCode 451中等哈希计数
根据字符出现频率排序 图解题解
这道题到底在问什么
给一个字符串 s，按字符出现次数从高到低重新排列，返回排序后的字符串。相同字符要挨在一起。
- s
- "loveleetcode"
- 输出
- "eeeelloovtcd"
- 说明
- e 出现 4 次排最前，l/o 各 2 次次之，v/t/c/d 各 1 次
最优解：一步一步想明白
- 3数 e 扫一遍、数 l 再扫一遍……每种字符都重扫全串，重复劳动太多。我们想要的是只扫一遍就把所有次数全数清。
- 4哈希表像一本点名册:字符是名字，值是「来了几次」。只走一遍，所有次数就全在册子上，这步只要 O(n)。下面用柱子把这一遍数清楚的过程演给你看。
- 57 种字符计数全为 0"loveleetcode" 里有 7 种不同字符 l o v e t c d。这 7 根柱子是它们的计数，现在都是 0。我们从左到右扫一遍，每见一个字符就把对应柱子升高 1。
- 6l: 0 → 1第 1 个字符是 l，点名册给 l 记一笔，l 的柱子升到 1。
- 7o: 0 → 1第 2 个是 o，第一次见，o 的柱子升到 1。
- 8v: 0 → 1第 3 个是 v，v 的柱子升到 1。
- 9e: 0 → 1第 4 个是 e，第一次见 e，e 的柱子升到 1。
- 10l: 1 → 2第 5 个又是 l，再给 l 记一笔，l 升到 2。重复的字符不新开格子，只是把已有计数 +1。
- 11e: 1 → 2第 6 个又是 e，e 升到 2。e 开始追上来了。
- 12e: 2 → 3第 7 个还是 e，e 升到 3，已经是最高的柱子了。
- 13t: 0 → 1第 8 个是 t，第一次见，t 的柱子升到 1。
- 14c: 0 → 1第 9 个是 c，第一次见，c 的柱子升到 1。
- 15o: 1 → 2第 10 个又是 o，o 升到 2，和 l 并列第二。
- 16d: 0 → 1第 11 个是 d，第一次见，d 的柱子升到 1。
- 17e: 3 → 4 · 全部数完最后第 12 个又是 e，e 升到 4!整串扫完，次数全清楚:e=4, l=2, o=2, v=1, t=1, c=1, d=1。只扫了一遍(O(n))。
- 1812 个字符 → 7 条计数哈希表里每个字符对应它的计数。只扫一遍就全数清，比反复数快得多。接下来就是按计数把字符排好队。
- 19要排的不是 12 个字符，而是 7 种不同字符，按它们的计数降序。种类少，排序很快。也可以用大顶堆每次取最多的，本质一样。
- 20e(4) > l(2)=o(2) > v=t=c=d(1)排序后柱子顺序变了:e(4) 排最前，l、o(各 2)次之，v、t、c、d(各 1)垫底。现在柱子从左到右的顺序，就是输出里字符块的顺序。
- 21e × 4 → "eeee"从计数最高的 e 开始取:e 出现 4 次，就把 4 个 e 一起拼上去。当前结果:eeee。
- 22l × 2 → "...ll"下一个是 l，出现 2 次，拼 2 个 l。当前结果:eeeell。
- 23o × 2 → "...oo"再取 o，也出现 2 次，拼 2 个 o。当前结果:eeeelloo。
- 24v × 1 → "...v"接下来都是 1 次的字符。先取 v，拼 1 个 v。当前结果:eeeelloov。
- 25t × 1 → "...t"取 t，拼 1 个 t。当前结果:eeeelloovt。
- 26c × 1 → "...c"取 c，拼 1 个 c。当前结果:eeeelloovtc。只剩最后一个 d 了。
- 27d × 1 → "eeeelloovtcd" ✓最后取 d，拼 1 个 d。所有字符放完，结果 = eeeelloovtcd，长度 12，和原串一样长，正是题目要的答案。
- 31错:e 只放 1 个如果拼接时每个字符只放一个，e 明明出现 4 次却只放 1 个，得到 elovtcd(长度才 7，原串是 12)——长度都不对。一定要 字符 × 计数。
⚠️ 容易写错的地方
✗ 错：拼接时每个字符只放一个
✓ 对：字符要重复它的计数那么多次
题目要相同字符挨在一起，e 出现 4 次就得放 "eeee"
✗ 错：按字符本身(字典序)排序
✓ 对：按字符的「计数」排序
排序的 key 是出现次数，不是字符的字典序
✗ 错：漏掉大小写/特殊字符
✓ 对：原样计入，区分大小写
'A' 和 'a' 是不同字符，各算各的
完整代码（Python / C++ / Java）
Python
from collections import Counter
class Solution:
def frequencySort(self, s):
cnt = Counter(s) # 扫一遍数次数
# 按计数从大到小排序字符
chars = sorted(cnt, key=lambda c: cnt[c], reverse=True)
res = []
for c in chars:
res.append(c * cnt[c]) # 字符 × 它的次数
return "".join(res)C++
class Solution {
public:
string frequencySort(string s) {
unordered_map<char,int> cnt;
for (char ch : s) cnt[ch]++; // 扫一遍数次数
vector<pair<char,int>> v(cnt.begin(), cnt.end());
sort(v.begin(), v.end(), [](const pair<char,int>& a, const pair<char,int>& b){
return a.second > b.second; // 按计数降序
});
string res;
for (size_t i = 0; i < v.size(); i++) res += string(v[i].second, v[i].first);
return res;
}
};Java
class Solution {
public String frequencySort(String s) {
Map<Character,Integer> cnt = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
cnt.put(ch, cnt.getOrDefault(ch, 0) + 1); // 数次数
}
List<Character> chars = new ArrayList<>(cnt.keySet());
chars.sort((a, b) -> cnt.get(b) - cnt.get(a)); // 按计数降序
StringBuilder sb = new StringBuilder();
for (char c : chars) {
for (int k = 0; k < cnt.get(c); k++) sb.append(c); // 字符 × 次数
}
return sb.toString();
}
}复杂度
时间复杂度
O(n + k log k)
数次数扫一遍 O(n);对 k 种不同字符排序 O(k log k)。k 是字符种类数(ASCII 最多 128)，很小
空间复杂度
O(n)
哈希表存 k 种字符的计数 O(k);结果字符串长度等于原串 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 根据字符出现频率排序 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用哈希表数次数而不是反复扫?+
哈希表让每个字符的 +1 都是 O(1)，整串只扫一遍 O(n);反复扫每种字符是 O(n²)。
排序解法和堆解法有什么区别?+
本质一样，都是按计数从大到小取。排序一次排好 O(k log k);大顶堆每次弹最大，取完也是 O(k log k)。
如果字符只可能是小写字母，能更快吗?+
能。用长度 26 的数组代替哈希表计数，再按计数排这 26 项，常数更小。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 根据字符出现频率排序 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。