451. Sort Characters By Frequency

Leetcode HashTable Heap

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();
}