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.
Example 2:
Input: "cccaaa" Output: "cccaaa" Explanation: Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer. Note that "cacaca" is incorrect, as the same characters must be together.
Example 3:
Input: "Aabb" Output: "bbAa" Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect. Note that 'A' and 'a' are treated as two different characters.
分析¶
基于桶排序:
public String frequencySort(String s) { if (s == null || s.length() == 0) return ""; char[] charArray = s.toCharArray(); // 统计出现次数 char[] frequency = new char[128]; int maxfrequency = 0; for (char c : charArray) if (++frequency[c] > maxfrequency) maxfrequency = frequency[c]; // 桶排序 List<List<Character>> buckets = new ArrayList<>(); for (int i = 0; i <= maxfrequency; i++) buckets.add(new ArrayList<>()); for (char c = 0; c < 128; c++) if (frequency[c] > 0) buckets.get(frequency[c]).add(c); // 依次从大到小去除元素 StringBuilder sb = new StringBuilder(); for (int i = maxfrequency; i > 0; i--) { List<Character> bucket = buckets.get(i); if (bucket.size() == 0) continue; for (int j = 0; j < bucket.size(); j++) for (int k = 0; k < i; k++) sb.append(bucket.get(j)); } return sb.toString(); }
近期评论