给定⼀个字符串,根据字符出现频率排序--Java实现
题⽬描述:
给定⼀个字符串,请将字符串⾥的字符按照出现的频率降序排列。
⽰例 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来存每个字符出现的次数(键为字符,值为出现的次数),再将map中的entry按值来从⼤到⼩排序,然后再连接起来(根据map 的值对应的key进⾏拼接)。
Map没有按值排序的⽅法,java有Comparator⽐较器接⼝,但要求的参数是list,我们可以通过Arraylist构造函数把Set()转化为list,就可以⽤⽐较器了。
Comparator⽐较器接⼝:
我们若需要控制某个类的次序,⽽该类本⾝不⽀持排序(即没有实现Comparable接⼝);我们可以建⽴⼀
个“⽐较器”来进⾏排序。这个“⽐较器”只需要实现Comparator接⼝即可。
Collections.sort(list, new PriceComparator())
参数⼀:需要排序的list
参数⼆:⽐较器,实现Comparator接⼝的类,返回⼀个int型的值,就相当于⼀个标志,告诉sort⽅法按什么顺序来对list进⾏排序。Comparator是个接⼝,可重写compare()及equals()这两个⽅法,⽤于⽐较功能;如果是null的话,就是使⽤元素的默认顺序,如
a,b,c,d,e,f,g,就是a,b,c,d,e,f,g这样,当然数字也是这样的。
compare(a,b)⽅法:根据第⼀个参数⼩于、等于或⼤于第⼆个参数分别返回负整数、零或正整数。
equals(obj)⽅法:仅当指定的对象也是⼀个 Comparator,并且强⾏实施与此 Comparator 相同的排序时才返回 true。
代码实现:
import java.util.*;
public class FrequencySort {
public static String frequencySort(String s) {
if (s.length() < 3){
return s;
}
     // 查表(将数据存到⼀个表⾥,然后查)map查⽐list更优(更适合查)
Map<Character, Integer> counter = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
counter.put(s.charAt(i), OrDefault(s.charAt(i), 0) + 1);
}
    //通过Arraylist构造函数把Set()转化为list(map没有按值排序的⽅法,我们要把map转化为list)
List<Map.Entry<Character, Integer>> list = new ArrayList<>(Set());
    //⽤Comparator⽐较器进⾏排序
Collections.sort(list, new Comparator<Map.Entry<Character, Integer>>() {
@Override
public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
          //从⼤到⼩逆序排序
Value() > o2.getValue() ? -1 : 1;
}
});
StringBuilder res = new StringBuilder();
     //遍历排好序的列表,得到排好序的集合,然后按值遍历,将键key放到res中,输出字符串)for (Map.Entry<Character, Integer> entry : list) {
       //对每⼀个值进⾏遍历,例如a出现三次,遍历3次,将a加⼊res,e出现2词,遍历2次,将e加⼊
for (int i = 0; i < Value(); i++) {
res.Key());
}
}
String();
}
public static void main(String[] args){
String str = "traaaee";
System.out.print(frequencySort(str));
字符串长度排序}
}

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。