leetcode-451-Sort-Characters-By-Frequency

发表于   |  

描述

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

1
2
3
4
5
6
7
8
9
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:

1
2
3
4
5
6
7
8
9
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:

1
2
3
4
5
6
7
8
9
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(Java)

先统计每个字符的数量，将字符，频率放入优先队列中，然后一个个从优先队列中取出来。

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
class Solution {
    public String frequencySort(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        Map<Character, Integer> charCountMap = new HashMap<Character, Integer>();
        PriorityQueue<Character> maxHeap = new PriorityQueue<Character>(s.length(), new Comparator<Character>(){
            public int compare(Character a, Character b){
                return charCountMap.get(b) - charCountMap.get(a);
            }
        });
        
        for (char c: s.toCharArray()) {
            charCountMap.put(c, charCountMap.getOrDefault(c, 0) + 1);
        }
        for (char c: charCountMap.keySet()) {
            maxHeap.offer(c);   
        }
        
        StringBuilder sb = new StringBuilder();
        while(maxHeap.size() > 0) {
            char c = maxHeap.poll();
            int charCount = charCountMap.get(c);
            while (charCount > 0) {
                sb.append(c);
                charCount--;
            }
        }
        return sb.toString();
    }
}

相关问题

题目来源