|
1
2
3
4
5
6
7
8
9
10
11
12
|
Given a string, sort it in decreasing order based on the frequency of characters.
Example 1:
Input:"tree"Output:"eert"Explanation:'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
Example 2:
Input:"cccaaa"Output:"cccaaa"Explanation:Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.
Example 3:
Input:"Aabb"Output:"bbAa"Explanation:"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.
|
题意：将字符串中字符按出现频率输出。
|
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
public
class
Solution {
public
String frequencySort(String s) {
if
(s==
null
|| s.length()<=
2
)
return
s;
int
length=s.length();
//统计各个字符出现的次数
HashMap<Character,Integer> map=
new
HashMap<Character,Integer>();
for
(
int
i=
0
;i<length;i++){
char
c=s.charAt(i);
if
(map.containsKey(c)){
map.put(c,map.get(c)+
1
);
}
else
{
map.put(c,
1
);
}
}
//sb1求出各种频率的字符
//"eeeee"的时候，e出现了length次，所以申请的时候length+1
StringBuilder[] sb1=
new
StringBuilder[length+
1
];
int
max=
0
;
for
(
char
c : map.keySet()){
int
fre=map.get(c);
if
(sb1[fre]==
null
){
sb1[fre]=
new
StringBuilder();
}
if
(fre>max)max=fre;
for
(
int
i=
0
;i<fre;i++){
sb1[fre].append(c);
}
}
//最后ret把各种频率的字符由高到低连接起来
StringBuilder ret=
new
StringBuilder();
for
(
int
i=max;i>
0
;i--){
if
(sb1[i]!=
null
)
ret.append(sb1[i]);
}
return
ret.toString();
//方法2；二维数组
int
[][] count=
new
int
[
128
][
2
];
char
[] ch=s.toCharArray();
for
(
char
c :ch){
count[c][
0
]=c;
count[c][
1
]++;
}
Arrays.sort(count,
new
Comparator<
int
[]>(){
public
int
compare(
int
[] a,
int
[]b){
return
b[
1
]-a[
1
];
}
});
StringBuilder ret=
new
StringBuilder();
for
(
int
i=
0
;i<
128
;i++){
for
(
int
j=
0
;j<count[i][
1
];j++){
ret.append((
char
)count[i][
0
]);
}
}
return
ret.toString();
}
}
|
PS：计算各个字符频率，拼接。。。
群里大神说有用heap，消化不了。。。
本文转自 努力的C 51CTO博客，原文链接:http://blog.51cto.com/fulin0532/1902228
