Given a string, sort it in decreasing order based on the frequency of characters.
Example 1:
Input: "tree" Output: "eert" Explanation: ‘e‘ appears twice while ‘r‘ and ‘t‘ both appear once. So ‘e‘ must appear before both ‘r‘ and ‘t‘. Therefore "eetr" is also a valid answer.
Solution 1: pq
class Solution { public String frequencySort(String s) { Map<Character, Integer> map = new HashMap<>(); for (Character c : s.toCharArray()) { map.put(c, map.getOrDefault(c, 0) + 1); } PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue()); pq.addAll(map.entrySet()); char[] charArr = new char[s.length()]; int i = 0; while (i < charArr.length) { Map.Entry<Character, Integer> entry = pq.poll(); Character cur = entry.getKey(); Integer times = entry.getValue(); int j = 0; while (j < times) { charArr[i + j] = cur; j += 1; } i += times; } return new String(charArr); } }
Solution 2: bucket sort based on Freqency
class Solution { public String frequencySort(String s) { Map<Character, Integer> map = new HashMap<>(); for (Character c : s.toCharArray()) { map.put(c, map.getOrDefault(c, 0) + 1); } // have a freq buckets from 0 to s.length, 0 is unused List<Character>[] buckets = new List[s.length() + 1]; for (char c : map.keySet()) { int times = map.get(c); if (buckets[times] == null) { buckets[times] = new LinkedList<>(); } buckets[times].add(c); } StringBuilder sb = new StringBuilder(); for (int i = buckets.length - 1; i >= 0; i--) { if (buckets[i] != null) { for (char ch: buckets[i]) { for (int j = 0; j < i; j++) { sb.append(ch); } } } } return sb.toString(); } }
[LC] 451. Sort Characters By Frequency
原文：https://www.cnblogs.com/xuanlu/p/12315495.html