https://leetcode-cn.com/problems/sort-characters-by-frequency/

描述

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

样例

  1. 输入:
  2. "tree"
  3. 输出:
  4. "eert"
  5. 解释:
  6. 'e'出现两次，'r'和't'都只出现一次。
  7. 因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
  9. 输入:
  10. "cccaaa"
  11. 输出:
  12. "cccaaa"
  13. 解释:
  14. 'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
  15. 注意"cacaca"是不正确的，因为相同的字母必须放在一起。
  17. 输入:
  18. "Aabb"
  19. 输出:
  20. "bbAa"
  21. 解释:
  22. 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
  23. 注意'A'和'a'被认为是两种不同的字符。

解题思路

  • 统计每个单词出现的频率，然后按频率进行排序，然后从频率大的开始拼接字符串。O(n + klogk)。k是有多少个不同字符

  • 看了题解有桶排序的方法，因为字符出现的频率是有上限的，所以把频率当成桶，往里填字符，最后从最大的桶开始拼接字符串

    AC代码

    1. public String frequencySort(String s) {
    2.   Map<Character, Integer> map = new HashMap<>();
    3.   char[] chars = s.toCharArray();
    4.   int max = 0;
    5.   for (int i = 0; i < s.length(); i++) {
    6.       int freq = map.getOrDefault(chars[i], 0) + 1;
    7.       map.put(chars[i], freq);
    8.       max = Math.max(max, freq);
    9.   }
    11.   StringBuilder[] build = new StringBuilder[max + 1];
    12.   for (int i = 0; i < max + 1; i++) {
    13.       build[i] = new StringBuilder();
    15.   }
    16.   for (Character ch : map.keySet()) {
    17.       build[map.get(ch)].append(ch);
    18.   }
    20.   StringBuilder ans = new StringBuilder();
    21.   for (int i = max; i >0 ; --i) {
    22.       if (build[i].length() > 0) {
    23.           for (Character ch : build[i].toString().toCharArray()) {
    24.               ans.append(String.valueOf(ch).repeat(map.get(ch)));
    25.           }
    26.       }
    27.   }
    28.   return ans.toString();
    29. }