Sort Characters by Frequency

时间：2017-02-19 16:48:29 阅读：238 评论：0 收藏：0 [点我收藏+]

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.

 1 public class Solution {
 2     public String frequencySort(String s) {
 3         HashMap<Character, Integer> map = new HashMap<Character, Integer>();
 4         for (int i = 0; i < s.length(); i++) {
 5             if (map.containsKey(s.charAt(i)))
 6                 map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
 7             else
 8                 map.put(s.charAt(i), 1);
 9         }
10         
11         PriorityQueue< Map.Entry<Character, Integer> > pq = new PriorityQueue<>(
12             new Comparator<Map.Entry<Character, Integer> >() {
13                 public int compare (Map.Entry<Character, Integer> a, Map.Entry<Character, Integer> b) {
14                     return b.getValue() - a.getValue();
15                 }
16             }
17         );
18         
19         pq.addAll(map.entrySet());
20         StringBuilder builder = new StringBuilder();
21         while (!pq.isEmpty()) {
22             Map.Entry entry = pq.poll();
23             int frequency = (int) entry.getValue();
24             for (int i = 0; i < frequency; i++) {
25                 builder.append(entry.getKey());
26             }
27         }
28         return builder.toString();
29     }
30 }

Sort Characters by Frequency

原文：http://www.cnblogs.com/amazingzoe/p/6416160.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)