Leetcode/G家，亚麻 -- 451. Sort Characters By Frequency(HashMap + Heap)

451. Sort Characters By Frequency

• Difficulty: Medium

https://leetcode.com/problems/sort-characters-by-frequency/
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.

思路1：Use HashMap<Character,Integer> to store char with its count.
           Use PriorityQueue with comparator to store character, max heap by count
           De Queue to print result map.get(c) times
思路2： Create 2nd map TreeMap to store the first map reversely, to sort map by value
             store key descending(new TreeMap<Integer,List<Character>>Collections.reverseOrder())  
Time Complexity: O(NlogN) because heap insertion O(lgN) do it N times
关键字： HashMap, PriorityQueue with comparator

public class Solution {
    public String frequencySort(String s) {
        if (s == null || s.length() <= 2) return s;
        StringBuilder res =new StringBuilder();
        HashMap<Character,Integer> map = new HashMap<Character,Integer>();
        PriorityQueue<Character> heap = new PriorityQueue<Character>(new Comparator<Character>(){
            @Override
            public int compare(Character c1, Character c2) {
                return map.get(c2) - map.get(c1);
            }
        });
        for(int i=0;i<s.length();i++){
            if(!map.containsKey(s.charAt(i))) map.put(s.charAt(i),0);
            map.put(s.charAt(i),map.get(s.charAt(i))+1);
        }
        for(Character key:map.keySet()) heap.offer(key);
        
        while(!heap.isEmpty()){//iterate map2 to print each char list for freq times
            Character c = heap.remove();
            int count = map.get(c);
            while(count>0){
                res.append(c);
                count--;
            }
        }
        return res.toString();
    }
}

解法2： 用TreeMap倒存再加到res
 

public class Solution {
    public String frequencySort(String s) {
        StringBuilder res =new StringBuilder();
        HashMap<Character,Integer> map = new HashMap<Character,Integer>();
        TreeMap<Integer,List<Character>> map2 = new TreeMap<Integer,List<Character>>(Collections.reverseOrder());
        for(int i=0;i<s.length();i++){
            if(!map.containsKey(s.charAt(i))) map.put(s.charAt(i),0);
            map.put(s.charAt(i),map.get(s.charAt(i))+1);
        }
        for(Character key:map.keySet()){
            int freq = map.get(key);
            if(!map2.containsKey(freq)) map2.put(freq,new ArrayList<Character>());
            map2.get(freq).add(key);
        }
        
        for(Integer freq:map2.keySet()){
            List<Character> tmp = map2.get(freq);
            for(Character c:tmp){
                int count = freq;
                while(count>0){
                    res.append(c);
                    count--;
                }
            }
        }
        return res.toString();
    }


}