返回
Featured image of post LeetCode 451 - 根据字符出现频率排序
Leetcode

LeetCode 451 - 根据字符出现频率排序

频率统计，计数排序.

[LeetCode] 451. Sort Characters By Frequency

题目：

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

示例 1:

输入: “tree”

输出: “eert”

解释: ‘e’出现两次，‘r’和’t’都只出现一次。 因此’e’必须出现在’r’和’t’之前。此外，“eetr"也是一个有效的答案。

示例2：

输入: “cccaaa”

输出: “cccaaa”

解释: ‘c’和’a’都出现三次。此外，“aaaccc"也是有效的答案。 注意"cacaca"是不正确的，因为相同的字母必须放在一起。

示例3：

输入: “Aabb”

输出: “bbAa”

解释: 此外，“bbaA"也是一个有效的答案，但"Aabb"是不正确的。 注意’A’和’a’被认为是两种不同的字符。

题解

思路1：HashMap计数+排序

字符串里的字符和出现频率形成一对K-V组合，解决按频率排序题目的第一思路是建一个HashMap统计出现频率，跟据一个从频率(Map的value)到原字符(Map的key)的反向映射，通过排序输出，主要步骤抽象如下：

  1. 使用HashMap记录字符出现的频率
  2. 将HashMap转化成List按value进行降序排序
  3. 遍历List，将字符按出现次数降序放入答案中

代码如下：

class Solution {
    public String frequencySort(String s) {
        StringBuilder sb = new StringBuilder();
        
        // 1. 使用HashMap记录字符出现的频率
        Map<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);
        }
        
        // 2. 将HashMap转化成List按value进行排序
        List<Map.Entry<Character, Integer>> l = new ArrayList<>(map.entrySet());
        Collections.sort(l, (o1, o2) -> {
            return o2.getValue() - o1.getValue();
        });

        //3. 遍历List，将字符按出现次数放入答案中
        for(Map.Entry<Character, Integer> entry : l){
            char c = entry.getKey();
            int time = entry.getValue();
            while(time-- > 0){
                sb.append(c);
            }
        }
        return sb.toString();

    }
}

时间复杂度：O(n+klogk) 空间复杂度：O(n+k)

这是一个不错的解题手法，向面试官展示了出色的API调用技术——当然我们还可以对时间复杂度进行优化：如果我们以字符出现的最大频率作为长度声明一个数组，用于存放每个频率出现过的字符，那么排序的时间复杂度可以进一步降低至O(k)，下面将介绍这种被称作桶排序的排序方法。

思路2：HashMap计数+桶排序

桶排序的思路网上比我讲解得更清楚，因此在此主要阐述针对该题的解题思路：

  1. 使用HashMap记录字符出现的频率，并记录字符出现的最大频率
  2. 创建桶，用于存放每个频率出现过的字符
  3. 遍历桶，将字符按出现次数降序放入答案中
class Solution {
    public String frequencySort(String s) {
        StringBuilder sb = new StringBuilder();
        
        //1 使用HashMap记录字符出现的频率，并记录字符出现的最大频率
        Map<Character, Integer> map = new HashMap<>();
        int max = 0;
        for(int i = 0; i < s.length(); i++){
            int curFreq = map.getOrDefault(s.charAt(i), 0) + 1;
            map.put(s.charAt(i), curFreq);
            max = Math.max(max, curFreq);
        }
        
        //2.1 创建桶
        List<Character>[] buckets = new ArrayList[max];
        for(int i = 0; i < max; i++){
            buckets[i] = new ArrayList<Character>();
        }
        //2.2 存放每个频率出现过的字符
        for(Map.Entry<Character, Integer> entry : map.entrySet()){
            buckets[entry.getValue() - 1].add(entry.getKey());
        }
        
        //3 遍历桶，将字符按出现次数降序放入答案中
        for(int i = max - 1; i >= 0; i--){
            for(char c : buckets[i]){
                for(int j = 0; j <= i; j++){
                    sb.append(c);
                }
            }
        }

        return sb.toString();

    }
}

时间复杂度：O(n+k) 空间复杂度：O(n+k)

和思路一主要的不同点是使用桶排序将排序的时间复杂度降到了k，做出了一些微小的贡献。但是在某些极端的面试官面前，我们的操作还是在库函数里边玩泥巴。我的室友就曾遇到过阿里的面试官死活不让调用HashMap的接口——“想要用哈希表就自己手写一个！”，对方如是说道。

手撸HashMap的确是有难度，但是对于这种规整的数据（ASCII码字符），也可以使用数组模拟Map的方法实现：声明一个长度为256位的数组，将出现的频率按照ASCII值存入数组即可。

思路2改进：数组模拟Map+桶排序

我们知道，HashMap效率并不高，加上Java的伪泛型设计，Map用起来并不如C++ STL那么方便，这道题统计频率的对象又是字符，最多不过0-256，完全可以用一个数组来进行统计。思路还是不变的。

  1. 使用Map数组记录字符出现的频率，并记录字符出现的最大频率
  2. 创建桶，用于存放每个频率出现过的字符
  3. 遍历桶，将字符按出现次数降序放入答案中
class Solution {
    public String frequencySort(String s) {
        if(s.length() < 3)
            return s;
        StringBuilder sb = new StringBuilder();
        
        //1 使用Map数组记录字符出现的频率，并记录字符出现的最大频率
        int[] map = new int[256];
        char[] arr = s.toCharArray();
        int max = 0;
        int length = s.length();
        for (char c : arr) {
            map[c]++;
            max = Math.max(max, map[c]);
        }
        
        //2.1 创建桶
        List<Character>[] buckets = new ArrayList[max];
        for(int i = 0; i < max; i++){
            buckets[i] = new ArrayList<Character>();
        }
        //2.2 存放每个频率出现过的字符
        for(int i = 0; i < 256; i++){
            if(map[i] > 0){
                buckets[map[i] - 1].add((char) i);
            }
        }
        
        //3 遍历桶，将字符按出现次数降序放入答案中
        for(int i = max - 1; i >= 0; i--){
            for(char c : buckets[i]){
                for(int j = 0; j <= i; j++){
                    sb.append(c);
                }
            }
        }

        return sb.toString();
    }
}

时间消耗从 22 ms 优化到 6 ms。

思路2改进：数组模拟Map+计数排序

这道题要求按序输出，我们可以直接进行计数排序，将时间复杂度降到 O(n) 。

参考数组reference[i]存的是出现i次字符的个数，用于输出时进行参考。再从头进行一次累加，从而确定在输出序列中的序号。这就是计数排序的思路。

public String frequencySort(String s) {
    if(s.length() < 3)
        return s;
    StringBuilder res = new StringBuilder();
    char[] arr = s.toCharArray();
    int[] map = new int[256];
    for (char c : arr) {
        map[c]++;
    }
    int maxOccurrence = 1, len = 0;
    int[] reference = new int[arr.length + 1];
    for (int occur : map) {
        if (occur > 0) {
            reference[occur]++;
            len++;
            if (occur > maxOccurrence) {
                maxOccurrence = occur;
            }
        }
    }
    for (int i = 1; i <= maxOccurrence; ++i) {
        reference[i] += reference[i - 1];
    }
    //我们先利用参考数组将所有字符进行排序，相同频率的字符放入时减一，从而错开位置。
    char[] dict = new char[len];
    for (char i = 0; i < 256; ++i) {
        if (map[i] > 0) {
            dict[len - 1 - --reference[map[i]]] = i;
        }
    }
    for (char tmp : dict) {
        for (int i = 0; i < map[tmp]; ++i) {
            res.append(tmp);
        }
    }
    return res.toString();
}

时间可以优化到 4 ms。

comments powered by Disqus
© 2020 - 2024 图拉国营噄茶馆