题目描述
给定一个字符串,请将字符串里的字符按照出现的频率降序排列。
样例
输入:
"tree"
输出:
"eert"
解释:
'e'出现两次,'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外,"eetr"也是一个有效的答案。
输入:
"cccaaa"
输出:
"cccaaa"
解释:
'c'和'a'都出现三次。此外,"aaaccc"也是有效的答案。
注意"cacaca"是不正确的,因为相同的字母必须放在一起。
输入:
"Aabb"
输出:
"bbAa"
解释:
此外,"bbaA"也是一个有效的答案,但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。
算法分析
- 用
pair
记录每个字符出现多少次,对pair[]
数组按照次数从小到大排序,枚举pair[]
数组,将字符出现了多少次连续拼接到结果中。例如a
字符出现2
次,拼接aa
时间复杂度 $O(nlogn)$
n = 128
Java 代码
class Solution {
public String frequencySort(String s) {
int n = s.length();
int[] c = new int[128];
for(int i = 0;i < n;i ++)
{
c[s.charAt(i)] ++;
}
Pair[] pair = new Pair[128];
for(int i = 0;i < 128;i ++)
{
pair[i] = new Pair(c[i], i);
}
Arrays.sort(pair, (x, y) -> {
return y.cnt - x.cnt;
});
StringBuilder sb = new StringBuilder();
for(int i = 0;i < 128;i ++)
{
char v = (char)pair[i].val;
while(pair[i].cnt > 0)
{
sb.append(v);
pair[i].cnt --;
}
}
return sb.toString();
}
}
class Pair
{
int cnt, val;
Pair(int cnt, int val)
{
this.cnt = cnt;
this.val = val;
}
}