首页 > 代码库 > Sort Characters By Frequency

Sort Characters By Frequency

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.

 1 public class Solution {
 2     public String frequencySort(String s) {
 3         HashMap<Character, Integer> charFreqMap = new HashMap<>();
 4         for (int i = 0; i < s.length(); i++) {
 5             char c = s.charAt(i);
 6             charFreqMap.put(c, charFreqMap.getOrDefault(c, 0) + 1);
 7         }
 8         ArrayList<Map.Entry<Character, Integer>> list = new ArrayList<>(charFreqMap.entrySet());
 9         
10         list.sort(new Comparator<Map.Entry<Character, Integer>>() {
11             public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
12                 return o2.getValue().compareTo(o1.getValue());
13             }
14         });
15         StringBuffer sb = new StringBuffer();
16         for (Map.Entry<Character, Integer> e : list) {
17             for (int i = 0; i < e.getValue(); i++) {
18                 sb.append(e.getKey());
19             }
20         }
21         return sb.toString();
22     }
23 }

 

Sort Characters By Frequency