|
题目描述: 给定一个字符串，请将字符串里的字符按照出现的频率降序排列。 示例 1： 输入:"tree" 输出:"eert" 解释:'e'出现两次，'r'和't'都只出现一次。因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。 示例 2： 输入:"cccaaa" 输出:"cccaaa" 解释:'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。 注意"cacaca"是不正确的，因为相同的字母必须放在一起。 示例 3： 输入:"Aabb" 输出:"bbAa" 解释:此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。注意'A'和'a'被认为是两种不同的字符。 题目分析: 用桶排序求解，跟LeetCode 347.前K个高频元素思路基本一致，差别在于需要把在list重复元素按重复次数取出来。首先创建字典集map，统计数组中的每个字符出现的次数，字符为键，出现的次数为值。然后创建list集合，遍历map，按照字符出现的次数作为下标，把键值放入list集合中。list集合为频次集合。最后创建返回的结果集，从大到小遍历list频次集，按频次取出元素返回即可。 题解(桶排序解法): 执行用时: 11 ms 内存消耗: 39.6 MB class Solution { public String frequencySort(String s) { // 先把字符串转换为字符数组，便于我们操作 char[] charArray = s.toCharArray(); // 创建结果集 char[] result = new char[s.length()]; // 使用字典，统计每个字符出现的次数，字符为键，元素出现的次数为值 HashMap<Character,Integer> map = new HashMap<>(); // 遍历数组 for (char c : charArray) // 统计元素出现次数 map.put(c,map.getOrDefault(c,0) + 1); // 创建list集合 List<Character>[] list = new List[charArray.length+1]; // 遍历map集合键集 for (Character c : map.keySet()) { // 如果list为空，则新建ArrayList if (list[map.get(c)] == null) list[map.get(c)] = new ArrayList<>(); // 获取键值出现的次数作为下标，把键放入list中 list[map.get(c)].add(c); } // 定义索引 int index = 0; // 从大到小遍历list频次数组集合 for (int j = list.length - 1; j > 0; j--) { // 如果当前不为空 if (list[j] != null) // 遍历当前list里面的元素 for (Character c : list[j]) { // 把元素放入结果集 for (int k = 0; k < j; k++) { result[index] = c; index++; } } } // 返回结果集 return String.valueOf(result); }}
|
