LC 451. 根据字符出现频率排序
题目描述
这是 LeetCode 上的 451. 根据字符出现频率排序 ,难度为 中等。
给定一个字符串,请将字符串里的字符按照出现的频率降序排列。
示例 1:
1 |
|
示例 2:
1 |
|
示例 3:
1 |
|
提示:
- $1 <= s.length <= 5 \times 10^5$
s
由大小写英文字母和数字组成
数据结构 + 模拟
这是一道考察数据结构运用的模拟题。
具体做法如下:
- 先使用「哈希表」对词频进行统计;
- 遍历统计好词频的哈希表,将每个键值对以
{字符,词频}
的形式存储到「优先队列(堆)」中。并规定「优先队列(堆)」排序逻辑为:- 如果
词频
不同,则按照词频
倒序; - 如果
词频
相同,则根据字符字典序
升序(由于本题采用 Special Judge 机制,这个排序策略随意调整也可以。但通常为了确保排序逻辑满足「全序关系」,这个地方可以写正写反,但理论上不能不写,否则不能确保每次排序结果相同);
- 如果
- 从「优先队列(堆)」依次弹出,构造答案。
代码:
1 |
|
- 时间复杂度:令字符集的大小为 $C$。使用「哈希表」统计词频的复杂度为 $O(n)$;最坏情况下字符集中的所有字符都有出现,最多有 $C$ 个节点要添加到「优先队列(堆)」中,复杂度为 $O(C\log{C})$;构造答案需要从「优先队列(堆)」中取出元素并拼接,复杂度为 $O(n)$。整体复杂度为 $O(\max(n, C\log{C}))$
- 空间复杂度:$O(n)$
数组实现 + 模拟
基本思路不变,将上述过程所用到的数据结构使用数组替代。
具体的,利用 ASCII 字符集共 $128$ 位,预先建立一个大小为 $128$ 的数组,利用「桶排序」的思路替代「哈希表」和「优先队列(堆)」的作用。
代码:
1 |
|
- 时间复杂度:令字符集的大小为 $C$,复杂度为 $O(\max(n, C\log{C}))$
- 空间复杂度:$O(n + C + \log{C})$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.451
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!