451. Sort Characters By Frequency
Last updated
Last updated
class Solution {
public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
PriorityQueue<Character> maxHeap = new PriorityQueue<>((a, b) -> map.get(b) - map.get(a));
maxHeap.addAll(map.keySet());
StringBuilder sb = new StringBuilder();
while (maxHeap.size() > 0) {
char key = maxHeap.remove();
for (int i = 0; i < map.get(key); i++) {
sb.append(key);
}
}
return sb.toString();
}
}
O(n), O(n)
// bucket 都會存 freq 在 array index (list array
// 所以大小都要宣告比 input
List<Character> bucket[] = new List[s.length() + 1];
// 之後依 bucket 尾巴開始取出, 因為有可能有些 freq index下
// 有些會沒資料 所以要判斷 null
for (int i = bucket.length - 1; i >= 0; i--) {
if (bucket[i] != null) {
// 不是 null 的 list, 就可以開始把某freq的值取出
for (char c : bucket[i]) {
for (int fr = 0; fr < i; fr++) { // 還要按數量印出
sb.append(c);
}
}
class Solution {
public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
List<Character> bucket[] = new List[s.length() + 1];
for (char c : map.keySet()) {
int freq = map.get(c);
if (bucket[freq] == null) {
bucket[freq] = new ArrayList<>();
}
bucket[freq].add(c);
}
StringBuilder sb = new StringBuilder();
for (int i = bucket.length - 1; i >= 0; i--) {
if (bucket[i] != null) {
for (char c : bucket[i]) {
for (int fr = 0; fr < i; fr++) {
sb.append(c);
}
}
}
}
return sb.toString();
}
}