题目描述:
给定一个字符串,请将字符串里的字符按照出现的频率降序排列。
示例 1:
输入:
“tree”
输出:
“eert”
解释:
'e’出现两次,'r’和’t’都只出现一次。
因此’e’必须出现在’r’和’t’之前。此外,"eetr"也是一个有效的答案。
示例 2:
输入:
“cccaaa”
输出:
“cccaaa”
解释:
'c’和’a’都出现三次。此外,"aaaccc"也是有效的答案。
注意"cacaca"是不正确的,因为相同的字母必须放在一起。
示例 3:
输入:
“Aabb”
输出:
“bbAa”
解释:
此外,"bbaA"也是一个有效的答案,但"Aabb"是不正确的。
注意’A’和’a’被认为是两种不同的字符。
代码:
jdk8之后对map的value之后变得更简单了,比如
这就实现了对value的升序
import java.util.Map;
import java.util.Map.Entry;
class Solution {
public String frequencySort(String s) {
// 按照value进行排序
Map<Character, Integer> map = new TreeMap();
for (int i = 0; i < s.length(); i++) {
char tem = s.charAt(i);
map.put(tem, map.getOrDefault(tem, 0) + 1);
}
List<Map.Entry<Character,Integer>>list = map.entrySet().stream()
.sorted((entry1, entry2) -> entry2.getValue().compareTo(entry1.getValue()))
.collect(Collectors.toList());
StringBuilder sb = new StringBuilder();
for (Entry<Character, Integer> entry : list) {
int get = entry.getValue();
char gets = entry.getKey();
for (int i = 0; i < get; i++) {
sb.append(gets);
}
}
return sb.toString();
}
}
当然也可以使用优先级队列来
import java.util.Map;
import java.util.Map.Entry;
class Solution {
public String frequencySort(String s) {
Map<Character, Integer> map = new TreeMap();
for (int i = 0; i < s.length(); i++) {
char tem = s.charAt(i);
map.put(tem, map.getOrDefault(tem, 0) + 1);
}
PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>(
(o1,o2) -> o2.getValue() - o1.getValue());
pq.addAll(map.entrySet());
int len=pq.size();
StringBuilder sb = new StringBuilder();
for(int i=0;i<len;i++){
char key=pq.peek().getKey(); //获取堆顶元素的键
int value=pq.poll().getValue();//获取并弹出堆顶元素的值
while(value-->0)
sb.append(key);
}
return sb.toString();
}
}
排名靠前的代码
这个设计的就挺好的
class Solution {
public String frequencySort(String s) {
StringBuilder sb = new StringBuilder();
int[] count = new int[256];
for (char c : s.toCharArray()) {
++count[c];
}
int[] clone = count.clone();
Arrays.sort(count);
for (int i = count.length - 1; i >= 0; i--) {
if (count[i] == 0) {
break;
}
for (int j = 0; j < clone.length; j++) {
if (clone[j] == count[i]) {
while (count[i]-- > 0) {
sb.append((char) j);
}
clone[j] = 0;
}
}
}
return sb.toString();
}
}