451. Sort Characters By Frequency

Sort Characters By Frequency - LeetCodeLeetCode

1. use maxHeap,

O(nlogm), m is the 26 char, so it's O(n), O(n)

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();
    }
}

2. use bucket sort

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();
        
    }
}