当前位置：首页 > article >正文

LeetCode题练习与总结：根据字符出现频率排序--451

article 2025/3/6 3:08:32

一、题目描述

给定一个字符串 s ，根据字符出现的频率对其进行 降序排序 。一个字符出现的频率是它出现在字符串中的次数。

返回 已排序的字符串 。如果有多个答案，返回其中任何一个。

示例 1:

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

示例 2:

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

示例 3:

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

提示:

1 <= s.length <= 5 * 10^5
s 由大小写英文字母和数字组成

二、解题思路

首先，我们需要统计每个字符在字符串中出现的频率。这可以通过使用一个哈希表（HashMap）来实现，其中键是字符，值是该字符出现的次数。
然后，我们需要根据字符出现的频率对字符进行排序。由于题目要求按照降序排序，我们可以使用优先队列（PriorityQueue）来实现。Java中的PriorityQueue默认是最小堆，因此我们需要自定义比较器来使其成为最大堆。
接下来，我们将所有字符放入优先队列中，队列会根据字符出现的频率自动排序。
最后，我们从优先队列中取出字符，按照其频率构造最终的字符串。

三、具体代码

import java.util.*;

class Solution {
    public String frequencySort(String s) {
        // 1. 统计字符频率
        Map<Character, Integer> frequencyMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }

        // 2. 使用优先队列对字符进行排序
        PriorityQueue<Character> pq = new PriorityQueue<>((a, b) -> frequencyMap.get(b) - frequencyMap.get(a));

        // 3. 将所有字符放入优先队列
        pq.addAll(frequencyMap.keySet());

        // 4. 构造结果字符串
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            char c = pq.poll();
            int frequency = frequencyMap.get(c);
            for (int i = 0; i < frequency; i++) {
                sb.append(c);
            }
        }

        return sb.toString();
    }
}

这段代码首先统计了每个字符的频率，然后使用优先队列对字符进行了降序排序，最后构造了结果字符串并返回。由于优先队列中元素的顺序是根据频率降序排列的，所以我们可以确保最终构造的字符串是满足题目要求的。

四、时间复杂度和空间复杂度

1. 时间复杂度

统计字符频率：我们遍历了字符串s一次，每次遍历都会更新哈希表frequencyMap。这个过程的时间复杂度是O(n)，其中n是字符串s的长度。
构建优先队列：我们将所有不同的字符放入优先队列中。由于字符串s中的字符种类最多为ASCII字符集的大小（通常为128或256），因此这一步的时间复杂度是O(m log m)，其中m是字符串中不同字符的数量。
构造结果字符串：我们从优先队列中取出每个字符，并按照其频率将其添加到结果字符串中。由于每个字符最多被添加到队列中一次，并且从队列中取出一次，因此这一步的时间复杂度是O(n log m)，其中n是字符串s的长度，m是字符串中不同字符的数量。

综合以上步骤，总的时间复杂度是O(n + m log m + n log m)。由于m ≤ n，因此可以简化为O(n log n)。

2. 空间复杂度

哈希表frequencyMap：用于存储每个字符及其出现的频率。在最坏的情况下，如果字符串s中的每个字符都不同，那么哈希表的大小将是O(m)，其中m是字符串中不同字符的数量。
优先队列pq：存储字符串中所有不同的字符。在最坏的情况下，优先队列的大小也是O(m)。
结果字符串sb：在构造结果字符串时，我们使用了StringBuilder，其空间复杂度是O(n)，其中n是字符串s的长度。

综合以上步骤，总的空间复杂度是O(m + n)，由于m ≤ n，因此可以简化为O(n)。

五、总结知识点

Java集合框架：
- HashMap：用于存储键值对，其中键是字符，值是该字符出现的次数。
- PriorityQueue：实现了优先队列，可以按照元素的自然顺序或者通过比较器（Comparator）来排序元素。
Lambda表达式：
- 在创建PriorityQueue时，使用了Lambda表达式来定义自定义的比较器，使得优先队列根据字符出现的频率降序排列。
方法引用：
- 使用了Character类的set作为addAll方法的参数，这是方法引用的一种形式，它将集合中的所有元素添加到优先队列中。
流的集合操作：
- frequencyMap.keySet()返回一个包含所有键的Set，然后使用addAll方法将其添加到优先队列中。
字符操作：
- 使用toCharArray()方法将字符串转换为字符数组，以便遍历每个字符。
HashMap操作：
- 使用getOrDefault方法来获取字符的频率，如果字符不存在于映射中，则返回默认值0。
循环和条件语句：
- 使用for循环来遍历字符数组，并更新字符频率。
- 使用while循环来处理优先队列中的元素，直到队列为空。
字符串构建：
- 使用StringBuilder来高效地构建最终的字符串结果，避免频繁的字符串连接操作。
优先队列操作：
- 使用poll方法从优先队列中移除并返回队列的头部元素，即当前频率最高的字符。
泛型：
- 在定义HashMap和PriorityQueue时使用了泛型，分别指定了键和值的类型。