LC 451 Sort Characters By Frequency(M)

Given a string, sort it in decreasing order based on the frequency of characters.

public String frequencySort(String s)

边界条件 如果字符串个数小于3,直接返回这个字符串。

解题思路 Map, Bucket Sort, PriorityQueue

1. 用map去统计各个字符出现的个数。

2. 把这个map 排序，可以用Bucket sort 或　PriorityQueue

3. 最后根据排序的map去生成字符串。

Bucket Sort Way

 public String frequencySort(String s) {
    if(s.length()<3)
        return s;
    // Step 1 count
    Map<Character, Integer> maps = new HashMap<Character, Integer>();
    for(char c : s.toCharArray()){
        if(!maps.containsKey(c)){
            maps.put(c, 1);
        }else{
            maps.put(c, maps.get(c) + 1);
        }
    }
    // Step 2 sort
    List<Character>[] bucket = new List[s.length() + 1];
    for(char key : maps.keySet()){
        int amount = maps.get(key);
        if(bucket[amount] == null){
            bucket[amount] = new ArrayList<Character>();
        }
        bucket[amount].add(key);
    }
    // Step 3 build
    StringBuilder sb = new StringBuilder();
    for(int i = bucket.length - 1; i > 0 ; i--){
        if(bucket[i] != null){
            for(char ch : bucket[i]){
                for(int j = 0; j < i; j++){
                    sb.append(ch);
                }
            }
        }
    }
    return sb.toString();
}

PriorityQueue Way

    // Step 2
    PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>(
        new Comparator<Map.Entry<Character, Integer>>() {
            @Override
            public int compare(Map.Entry<Character, Integer> a, Map.Entry<Character, Integer> b) {
                return b.getValue() - a.getValue();
            }
        }
    );    
    pq.addAll(map.entrySet());

    // Step 3;
    StringBuilder sb = new StringBuilder();
    while (!pq.isEmpty()) {
        Map.Entry e = pq.poll();
        for (int i = 0; i < (int)e.getValue(); i++) {
            sb.append(e.getKey());
        }
    }