LeetCode451根据字符出现频率排序

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
示例 1:
输入:
“tree”
输出:
“eert”
解释:
'e’出现两次，'r’和’t’都只出现一次。
因此’e’必须出现在’r’和’t’之前。此外，"eetr"也是一个有效的答案。
示例 2:
输入:
“cccaaa”
输出:
“cccaaa”
解释:
'c’和’a’都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。
示例 3:
输入:
“Aabb”
输出:
“bbAa”
解释:
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意’A’和’a’被认为是两种不同的字符。

解题思路：创建两个对象，map:统计每个字符出现次数，List[] sort：将出现次数相同的字符加到一个List中，出现的次数即为数组的索引，值为相应的元素列表
代码如下：

public static String frequencySort(String s) {
int len = s.length();
Map<String, Integer> map = new HashMap<>();
List<String>[] sort = new LinkedList[len + 1];
for (int i = 0; i < len; i++){
String stmp = s.substring(i,i+1);
map.put(stmp, map.getOrDefault(stmp, 0) + 1);
}
for (Map.Entry<String, Integer> entry : map.entrySet()){
Integer value = entry.getValue();
if (sort[value] == null){
sort[value] = new LinkedList<>();
}
sort[value].add(entry.getKey());
}
StringBuilder sb = new StringBuilder();
for (int i = sort.length - 1; i >= 0; i--){
if (sort[i] == null){
continue;
}
int cSize = sort[i].size();
for (int j = 0; j <cSize; j++){
for (int k =0; k < i; k++){
sb.append(sort[i].get(j));
}
}
}
return sb.toString();
}

解法二： 堆排序

class Solution {
public String frequencySort(String s) {
//初始化字母数组
int[] latters = new int[256];
//填充数组
for(char c:s.toCharArray()){
latters[c]++;
}
//排序,将出现次数大的放到队列的头部
PriorityQueue<Letter> queue = new PriorityQueue<>();
for (int i = 0;i<latters.length;i++){
if (latters[i]!=0){
queue.add(new Letter((char) i,latters[i]));
}
}
StringBuilder stringBuilder = new StringBuilder();
//依次将元素排出
while (!queue.isEmpty()){
Letter letter = queue.poll();
for (int i =0;i<letter.count;i++)
stringBuilder.append(letter.latter);
}
return stringBuilder.toString();
}
public class Letter implements Comparable<Letter>{
public char latter = '0';
public int count = 0;
public Letter(char latter, int count) {
this.latter = latter;
this.count = count;
}
@Override
public int compareTo(Letter o) {
return o.count - this.count;
}
}
}

最后

以上就是优雅飞鸟为你收集整理的LeetCode451根据字符出现频率排序的全部内容，希望文章能够帮你解决LeetCode451根据字符出现频率排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。