算法-根据字符出现频率排序1、根据字符出现频率排序

96 阅读 0 评论 64 点赞

我是靠谱客的博主幸福咖啡，这篇文章主要介绍算法-根据字符出现频率排序1、根据字符出现频率排序，现在分享给大家，希望可以做个参考。

算法-根据字符出现频率排序

1、根据字符出现频率排序

1、根据字符出现频率排序

451. 根据字符出现频率排序

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
示例 1:
输入:
"tree"
输出:
"eert"
解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
示例 2:
输入:
"cccaaa"
输出:
"cccaaa"
解释:
'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。
示例 3:
输入:
"Aabb"
输出:
"bbAa"
解释:
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。

本题是一个自hash的绝佳案例,完全可以利用Hash表的性质将时间复杂度优化为O(N)
主要思想是建立一个counter数组，数组索引为字符的ASCII码值，数组内容为字符出现的次数，然后我们每次都去搜索数组中最大的元素，搜索完成后将最大元素的出现次数置为0(记忆化搜索)，由于字符处于0-128之间，我们查找时间复杂度实际为O(1).因此，总时间复杂度为O(N)。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public String frequencySort(String s) {
if(s==null){
return s;
}
int[] counter=new int[128];//自hash，统计字符出现次数
char[] cs=s.toCharArray();
for(char c:cs){
counter[c]++;
}
int curr=0;
while (curr<cs.length){
int[] result=findMax(counter);//寻找出现次数最多的元素，返回元素和元素出现次数，时间复杂度O(128)也就是O(1)
char c=(char) result[0];//找到的元素
int count=result[1];//元素出现次数
while (count-->0){
cs[curr++]=c;//填充数据
}
}
return new String(cs);
}
public int[] findMax(int[] counter){
int count=0;
int index=0;
for(int i=0;i<='z';i++){
if(counter[i]>count){
count=counter[i];
index=i;
}
}
counter[index]=0;//使用完了，下次不再使用了
return new int[]{index,count};
}

执行的速度也是极快的，目前leetcode除我之外，最快速度是3ms，而我的算法达到了2ms

复制代码

1
2
3
执行用时 :2 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗 :40.3 MB, 在所有 Java 提交中击败了11.11%的用户

其实本算法还有可以优化的地方，指出两点：
1、函数调用有调用栈开销，因此可以将每次寻找最大值的地方放到循环体里面去，而不是使用一个子函数
2、本方法时间复杂度虽然为O(N)，但是其实还是可以改进的，我们只对出现过的字符进行判断就好了。

针对第1点，可以做如下优化

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public String frequencySort(String s) {
if(s==null){
return s;
}
int[] counter=new int[128];//自hash，统计字符出现次数
char[] cs=s.toCharArray();
for(char c:cs){
counter[c]++;
}
int curr=0;
while (curr<cs.length){
int count=0;
char c=0;
//下面的for循环，时间复杂度为O(1)，因为最坏情况下遍历次数为'z'=122次
for(int i=0;i<='z';i++){
if(counter[i]>count){
count=counter[i];
c=(char)i;
}
}
counter[c]=0;//使用完了，下次不再使用了
while (count-->0){
cs[curr++]=c;//填充数据
}
}
return new String(cs);
}