leetcode 451. 根据字符出现频率排序
题目：451. 根据字符出现频率排序
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。。
示例1:
输入: “tree”
‘e’出现两次，’r’和’t’都只出现一次。
因此’e’必须出现在’r’和’t’之前。此外，”eetr”也是一个有效的答案。
示例2:
输入: “cccaaa”
‘c’和’a’都出现三次。此外，”aaaccc”也是有效的答案。
注意”cacaca”是不正确的，因为相同的字母必须放在一起。
示例3:
输入: “Aabb”
此外，”bbaA”也是一个有效的答案，但”Aabb”是不正确的。
注意’A’和’a’被认为是两种不同的字符。
方法一：堆排序（大顶堆） 思路： 使用PriorityQueue,维护大顶堆。通过HashMap记录每个字符的出现次数，通过维护大顶堆将出现频率按从大到小的顺序遍历字符，在遍历过程中将字符（出现次数个字符）追加到记录结果的StringBuilder里面。
运行数据： 执行用时：15 ms，内存消耗：40.7 MB
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 String frequencySort (String s) Map<Character, Integer> map = new HashMap<Character, Integer>(); for (char ch : s.toCharArray()) { map.put(ch, map.getOrDefault(ch, 0 ) + 1 ); } PriorityQueue<Character> queue = new PriorityQueue<>((o1,o2)->(map.get(o2) - map.get(o1))); queue.addAll(map.keySet()); StringBuilder builder = new StringBuilder(); while (!queue.isEmpty()) { char key = queue.poll(); int count = map.get(key); while (count-- > 0 ) { builder.append(key); } } return builder.toString(); }
方法二：堆排序（大顶堆），数组替换HashMap 思路： 使用PriorityQueue,维护大顶堆，在方法一的基础上进行优化，使用数组替换HashMap记录字符出现的次数。
运行数据： 执行用时：5 ms，内存消耗：40.6 MB
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 public String frequencySort (String s) int [] freq = new int [256 ]; for (char ch : s.toCharArray()) { freq[ch]++; } PriorityQueue<Character> queue = new PriorityQueue<>((o1,o2)->(freq[o2] - freq[o1])); for (int i = 0 ; i < freq.length; i++) { if (freq[i] == 0 ) continue ; queue.offer((char )i); } StringBuilder builder = new StringBuilder(); while (!queue.isEmpty()) { char key = queue.poll(); int count = freq[key]; while (count-- > 0 ) { builder.append(key); } } return builder.toString(); }
方法三：桶排序 思路： 桶排序，将出现频率相同的放到一个桶中。通过数组记录每个字符的出现次数，在进行分桶之后，依次按出现频率从大到小遍历桶，遍历桶中的元素，在遍历桶中元素的过程中将字符（出现次数个字符）追加到记录结果的StringBuilder里面。
运行数据： 执行用时：10 ms，内存消耗：41.4 MB
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 String frequencySort (String s) int [] freq = new int [256 ]; for (char ch : s.toCharArray()) { freq[ch]++; } List<Character>[] arr = new ArrayList[s.length() + 1 ]; for (int i = 0 ; i < freq.length; i++) { if (freq[i] == 0 ) continue ; if (arr[freq[i]] == null ) { arr[freq[i]] = new ArrayList<>(); } arr[freq[i]].add((char )i); } StringBuilder builder = new StringBuilder(); for (int i = arr.length - 1 ; i > 0 ; i--) { if (arr[i] == null ) continue ; for (Character item : arr[i]) { int t = i; while (t-- > 0 ) { builder.append(item); } } } return builder.toString(); }
学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。
才疏学浅，若有错误或不当之处，可批评指正，还请见谅！
