451 Sort Characters By Frequency

1. Question

Given a string, sort it in decreasing order based on the frequency of characters.
Example 1:
1
Input: "tree"
2
3
Output: "eert"
4
5
Explanation:
6
'e' appears twice while 'r' and 't' both appear once.
7
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
Copied!
Example 2:
1
Input: "cccaaa"
2
3
Output: "cccaaa"
4
5
Explanation:
6
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
7
Note that "cacaca" is incorrect, as the same characters must be together.
Copied!
Example 3:
1
Input: "Aabb"
2
3
Output: "bbAa"
4
5
Explanation:
6
"bbaA" is also a valid answer, but "Aabb" is incorrect.
7
Note that 'A' and 'a' are treated as two different characters.
Copied!

2. Implementation

(1) Bucket Sort
1
class Solution {
2
public String frequencySort(String s) {
3
if (s == null || s.length() <= 1) {
4
return s;
5
}
6
7
int[] map = new int[256];
8
9
for (char c : s.toCharArray()) {
10
map[c]++;
11
}
12
13
List<Character> bucket[] = new List[s.length() + 1];
14
15
for (char key = 0; key < map.length; key++) {
16
if (map[key] != 0) {
17
int freq = map[key];
18
19
if (bucket[freq] == null) {
20
bucket[freq] = new ArrayList<>();
21
}
22
bucket[freq].add(key);
23
}
24
}
25
26
StringBuilder res = new StringBuilder();
27
for (int i = bucket.length - 1; i >= 0; i--) {
28
if (bucket[i] != null) {
29
for (char c : bucket[i]) {
30
while (map[c]-- > 0) {
31
res.append(c);
32
}
33
}
34
}
35
}
36
return res.toString();
37
}
38
}
Copied!
(2) Heap
1
class Solution {
2
public String frequencySort(String s) {
3
if (s == null || s.length() == 0) {
4
return "";
5
}
6
7
int[] map = new int[256];
8
9
for (char c : s.toCharArray()) {
10
++map[c];
11
}
12
13
PriorityQueue<CharInfo> maxHeap = new PriorityQueue<>();
14
15
for (int i = 0; i < 256; i++) {
16
if (map[i] != 0) {
17
maxHeap.add(new CharInfo((char)i, map[i]));
18
}
19
}
20
21
StringBuilder res = new StringBuilder();
22
23
while (!maxHeap.isEmpty()) {
24
CharInfo curChar = maxHeap.remove();
25
26
while (--curChar.freq >= 0) {
27
res.append(curChar.val);
28
}
29
}
30
return res.toString();
31
}
32
33
class CharInfo implements Comparable<CharInfo> {
34
char val;
35
int freq;
36
37
public CharInfo(char val, int freq) {
38
this.val = val;
39
this.freq = freq;
40
}
41
42
public int compareTo(CharInfo that) {
43
return that.freq - this.freq;
44
}
45
}
46
}
Copied!

3. Time & Space Complexity

Bucket Sort: 时间复杂度O(n), 空间复杂度O(n)
Heap: 时间复杂度O(n), 空间复杂度O(n)