leetcode

LeetCode 451. Sort Characters By Frequency

Problem

LeetCode 451. Sort Characters By Frequency

1. 题目简述

给出一个字符串，将其字母按照字母出现频率进行降序排列。例如：

Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

2. 算法思路

HashTable：

一考虑到频率的问题，首先就应该想到hashmap来进行计算。然后比较麻烦的是对hashmap的value进行排序，这个需要重写一个comparator，用来排序Map.Entry，写的比较少，多练练。然后按照顺序输出就可以了。

时间复杂度为O(nlogn)，这个是排序的时间复杂度；空间复杂度最大为O(n).

Bucket Sort：

第二种做法是用bucket sort，将字符放入hashmap后，计算出最大频率freq，然后简历一个长度为freq+1的list，对于不同频率的字符放入其中。

3. 解法

  1. HashTable

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> dict = new HashMap();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            dict.put(c, dict.getOrDefault(c, 0) + 1);
        }

        // 重点在这里！！！Comparator的写法，以及如何对hashmap转为list后排序
        List<Map.Entry<Character, Integer>> list = new ArrayList(dict.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<Character, Integer>>(){
            public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
                return o2.getValue() - o1.getValue();
            }
        });

        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Character, Integer> entry : list) {
            int copy = entry.getValue();
            char c = entry.getKey();
            while (copy > 0) {
                sb.append(c);
                copy--;
            }
        }

        return sb.toString();
    }
}
  1. Bucket Sort

这里要注意三个地方：见注释。

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> dict = new HashMap();
        int maxFrequency = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            dict.put(c, dict.getOrDefault(c, 0) + 1);
            maxFrequency = Math.max(maxFrequency, dict.get(c));
        }

        int size = dict.size();
        // 注意1：这里定义数组时不用初始化，抽象定义
        List<Character>[] bucket = new List[maxFrequency + 1];

        for (Map.Entry<Character, Integer> entry : dict.entrySet()) {
            // 注意2：这路记得初始化bucket数组
            if (bucket[entry.getValue()] == null) {
                bucket[entry.getValue()] = new ArrayList();
            }
            bucket[entry.getValue()].add(entry.getKey());
        }

        StringBuilder sb = new StringBuilder();
        for (int i = maxFrequency; i > 0; i--) {
            // 注意3：bucket数组可能未被初始化，这里需要判断是否为空
            for (Character character : bucket[i]) {
                for (int j = i; j > 0; j--) {
                    sb.append(character.charValue());
                }
            }
        }

        return sb.toString();
    }
}