LeetCode451-根据字符出现频率排序

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/sort-characters-by-frequency/

中文链接：https://leetcode-cn.com/problems/sort-characters-by-frequency/

题目详述

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

    示例 1:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    输入:
    "tree"

    输出:
    "eert"

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

    示例 2:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    输入:
    "cccaaa"

    输出:
    "cccaaa"

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

    示例 3:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    输入:
    "Aabb"

    输出:
    "bbAa"

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

题目详解

本题与 LeetCode347-前K个高频元素 思路是一致的，首先要统计每个字符的出现次数，构造一个从数据到出现次数的映射，据此来进行比较。

方法一：利用桶排序，时间复杂度为 O(n)。

  • 把元素出现次数作为桶的下标，元素作为桶的数据。
  • 从后往前遍历桶，就是从频率高到频率低进行遍历，拼接得到结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class LeetCode_00451 {

    // 时间复杂度为 O(n)
    public String frequencySort(String s) {
        // 构建字符到出现次数的映射
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        // 构建桶，桶的下标表示出现次数
        List<Character>[] buckets = new ArrayList[s.length() + 1];
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            char c = entry.getKey();
            int count = entry.getValue();
            if (buckets[count] == null) {
                buckets[count] = new ArrayList<>();
            }
            buckets[count].add(c);
        }
        // 从后往前（频率高到频率低）遍历，拼接得到结果
        StringBuilder sb = new StringBuilder();
        for (int i = buckets.length - 1; i >= 0; --i) {
            if (buckets[i] != null) {
                for (char c : buckets[i]) {
                    for (int j = 0; j < i; ++j) {
                        sb.append(c);
                    }
                }
            }
        }
        return sb.toString();
    }
}

方法二：利用快排，时间复杂度为 O(nlogn)。

  • 将元素与出现次数的 Map 转换为 List。
  • 调用 Collections.sort 进行排序，排序依据的是字符的的出现次数。
  • 遍历拼接得到结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class LeetCode_00451 {

    // 时间复杂度为 O(nlogn)
    public String frequencySort(String s) {
        // 构建字符到出现次数的映射
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        // 将 Map 转为 List
        List<Map.Entry<Character, Integer>> list = new ArrayList<>(map.entrySet());
        // 根据出现次数从大到小排序
        Collections.sort(list, (o1, o2) -> Integer.compare(o2.getValue(), o1.getValue()));
        // 拼接得到结果
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Character, Integer> entry : list) {
            char c = entry.getKey();
            int count = entry.getValue();
            while (count-- != 0) {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}