【leetcode451】【hashmap+桶排序】按照字符出现次数对字符串排序
程序员文章站
2022-05-12 16:15:26
...
题目
给定一个字符串,请将字符串里的字符按照出现的频率降序排列。
示例 1:
输入:
“tree”
输出:
“eert”
解释:
'e’出现两次,'r’和’t’都只出现一次。
因此’e’必须出现在’r’和’t’之前。此外,"eetr"也是一个有效的答案。
示例 2:
输入:
“cccaaa”
输出:
“cccaaa”
解释:
'c’和’a’都出现三次。此外,"aaaccc"也是有效的答案。
注意"cacaca"是不正确的,因为相同的字母必须放在一起。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sort-characters-by-frequency
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
1.hashmap存储
2.桶排序
代码
import java.util.*;
class Solution {
public String frequencySort(String s) {
Map<Character,Integer> map = new HashMap<>();
for(char c:s.toCharArray()){
map.put(c,map.getOrDefault(c,0)+1);
}
List<Character>[] buckets = new ArrayList[s.length()+1];
for(char c:map.keySet()){
int num = map.get(c);
if(buckets[num]==null){
buckets[num] = new ArrayList<>();
}
buckets[num].add(c);
}
StringBuilder str = new StringBuilder();
for(int i=buckets.length-1;i>=0;i--){
if(buckets[i]==null){
continue;
}
for(char c:buckets[i]){
for(int j=0;j<i;j++){
str.append(c);
}
}
}
return str.toString();
}
}
总结
上一篇: Android MVC和MVP架构的详解
下一篇: Android 架构:MVP实践