题目描述

给定一个字符串,请将字符串里的字符按照出现的频率降序排列。


解题思路:

  1. 桶排序
  2. 使用StringBuilder将桶中的字符不断添加进去
    static String frequencySort(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }
        List<Character>[] lists = new List[s.length() + 1];
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            Character key = entry.getKey();
            Integer value = entry.getValue();
            if (lists[value] == null) {
                lists[value] = new ArrayList<>();
            }
            lists[value].add(key);
        }
        StringBuilder str = new StringBuilder();
        for (int i = lists.length - 1; i >= 0; i--) {
            if (lists[i] == null) {
                continue;
            }
            for (char c : lists[i]) {
                for (int j = 0; j < i; j++) {
                    str.append(c);
                }
            }
        }
        return str.toString();
    }

Q.E.D.