原文链接: https://leetcode-cn.com/problems/sort-characters-by-frequency

英文原文

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

 

Example 1:

复制

Input: s = "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: s = "cccaaa"
Output: "aaaccc"
Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

复制

Input: s = "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.

 

Constraints:

• 1 <= s.length <= 5 * 105
• s consists of uppercase and lowercase English letters and digits.

中文题目

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

示例 1:

复制

输入:
"tree"

输出:
"eert"

解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

示例 2:

复制

输入:
"cccaaa"

输出:
"cccaaa"

解释:
'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。

示例 3:

复制

输入:
"Aabb"

输出:
"bbAa"

解释:
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。

通过代码

高赞题解

数据结构 + 模拟

这是一道考察数据结构运用的模拟题。

具体做法如下：

1. 先使用「哈希表」对词频进行统计；
2. 遍历统计好词频的哈希表，将每个键值对以 {字符,词频} 的形式存储到「优先队列（堆）」中。并规定「优先队列（堆）」排序逻辑为：
   • 如果 词频 不同，则按照 词频 倒序；
   • 如果 词频 相同，则根据 字符字典序 升序（由于本题采用 Special Judge 机制，这个排序策略随意调整也可以。但通常为了确保排序逻辑满足「全序关系」，这个地方可以写正写反，但理论上不能不写，否则不能确保每次排序结果相同）；
3. 从「优先队列（堆）」依次弹出，构造答案。

image.png

代码：

复制

[]
class Solution {
    class Node {
        char c; 
        int v;
        Node(char _c, int _v) {
            c = _c; v = _v;
        }
    }
    public String frequencySort(String s) {
        char[] cs = s.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        for (char c : cs) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        PriorityQueue<Node> q = new PriorityQueue<>((a,b)->{
            if (b.v != a.v) return b.v - a.v;
            return a.c - b.c;
        });
        for (char c : map.keySet()) {
            q.add(new Node(c, map.get(c)));
        }
        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            Node poll = q.poll();
            int k = poll.v;
            while (k-- > 0) sb.append(poll.c);
        }
        return sb.toString();
    }
}

• 时间复杂度：令字符集的大小为 $C$。使用「哈希表」统计词频的复杂度为 $O(n)$；最坏情况下字符集中的所有字符都有出现，最多有 $C$ 个节点要添加到「优先队列（堆）」中，复杂度为 $O(C\log{C})$；构造答案需要从「优先队列（堆）」中取出元素并拼接，复杂度为 $O(n)$。整体复杂度为 $O(\max(n, C\log{C}))$
• 空间复杂度：$O(n)$

---

数组实现 + 模拟

基本思路不变，将上述过程所用到的数据结构使用数组替代。

具体的，利用 ASCII 字符集共 $128$ 位，预先建立一个大小为 $128$ 的数组，利用「桶排序」的思路替代「哈希表」和「优先队列（堆）」的作用。

image.png

代码：

复制

[]
class Solution {   
    public String frequencySort(String s) {
        int[][] cnts = new int[128][2];
        char[] cs = s.toCharArray();
        for (int i = 0; i < 128; i++) cnts[i][0] = i;
        for (char c : cs) cnts[c][1]++;
        Arrays.sort(cnts, (a, b)->{
            if (a[1] != b[1]) return b[1] - a[1];
            return a[0] - b[0];
        });
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 128; i++) {
            char c = (char)cnts[i][0];
            int k = cnts[i][1];
            while (k-- > 0) sb.append(c);
        }
        return sb.toString();
    }
}

• 时间复杂度：令字符集的大小为 $C$。复杂度为 $O(\max(n, C\log{C}))$
• 空间复杂度：$O(n + C + \log{C})$

统计信息

通过次数	提交次数	AC比率
85911	120666	71.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
前 K 个高频元素	中等
字符串中的第一个唯一字符	简单