package 队列.优先级队列;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
/**
 * https://leetcode-cn.com/problems/sort-characters-by-frequency/
 * 
 * @author Huangyujun
 *
 *         出现频率：哈希表【当前字母 ，次数】 优先队列【】
 */
public class _451_根据字符出现频率排序 {
    /**
     * 官网解法：与我相比：//取出所有的key【字符】构成一个集合，【通过map.get(字符)】进行降序排序 List<Character> list =
     * new ArrayList<Character>(map.keySet()); Collections.sort(list, (a, b) ->
     * map.get(b) - map.get(a));
     * 
     * @author Huangyujun
     *
     */
    class Solution2 {
        public String frequencySort(String s) {
            Map<Character, Integer> map = new HashMap<Character, Integer>();
            int length = s.length();
            for (int i = 0; i < length; i++) {
                char c = s.charAt(i);
                int frequency = map.getOrDefault(c, 0) + 1;
                map.put(c, frequency);
            }
            // 取出所有的key【字符】构成一个集合，【通过map.get(字符)】进行降序排序
            // 然后 stringBuffer 进行拼接
            List<Character> list = new ArrayList<Character>(map.keySet());
            Collections.sort(list, (a, b) -> map.get(b) - map.get(a));
            StringBuffer sb = new StringBuffer();
            int size = list.size();
            for (int i = 0; i < size; i++) {
                char c = list.get(i);
                int frequency = map.get(c);
                for (int j = 0; j < frequency; j++) {
                    sb.append(c);
                }
            }
            return sb.toString();
        }
    }
    /**
     * 我卡壳的解法：缺少了一些知识储备：通过entrySet 取到结点集合
     * ArrayList<Character>(map.keySet()); Collections.sort(list, (a, b) ->
     * map.get(b) - map.get(a));
     */
//    public String frequencySort(String s) {     
//        HashMap<Character, Integer> map = new HashMap<>();
//        int len = s.length();
//        for(int i = 0; i < len; i++) {
//            Character ch = s.charAt(i);
//            if(map.containsKey(ch)) {
//                int count = map.get(ch);
//                map.put(ch, count);
//            }else {
//                map.put(ch, 1);
//            }
//        }
//        StringBuffer sb = new StringBuffer();
//        int size = map.size();//无法通过value得到key呀, 通过keySet 拿出所有的 key构成集合，然后，通过工具类Collections 进行排序
//        for(int i = 0; i < size - 1; i++) {
//            //假设当前是最大数
//            int count = map.get(i);
//        
//            for(int j = 1; j < size; j++) {
//                if(count < map.get(j)) {
//                    count = map.get(j);
//                }
//            }
//            
//        }
//        return null;        
//    }
}