451. Sort Characters By Frequency

451. 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.

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.

My Solutions:

用hash 存贮每个char的频率，然后按照从大到小依次把char加入最终结果。有三种写法：

1。 吊桶：循环所有出现的char

2。 PriorityQueue

3。吊桶：只循环128个unicode (最快）

方法1:

class Solution {
    public String frequencySort(String s) {
        
        HashMap<Character, Integer> hash = new HashMap<>();
        for (char c : s.toCharArray()) {
            hash.put(c, hash.getOrDefault(c, 0) + 1);
        }
        
        //use bucket to store numbers by frequency
        List<Character>[] bucket = new ArrayList[s.length() + 1];
        for (char c : hash.keySet()) {
            int count = hash.get(c);
            if (bucket[count] == null) bucket[count] = new ArrayList<>();
            bucket[count].add(c);
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = bucket.length - 1; i > 0; i--) {
            if (bucket[i] != null) {
                for (char c : bucket[i]) {
                    for (int j = i; j > 0; j--) sb.append(c);
                }
            }
        }
        return sb.toString();
    }
}

方法2:

public class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        
        //sort frequency by a priority queue
        PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>(
            new Comparator<Map.Entry<Character, Integer>>() {
                @Override
                public int compare(Map.Entry<Character, Integer> a, Map.Entry<Character, Integer> b) {
                    if (a.getValue() != b.getValue()) return b.getValue() - a.getValue();
                    else return a.getKey().compareTo(b.getKey());
                }
            }
        );
        
        pq.addAll(map.entrySet());
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            Map.Entry e = pq.poll();
            for (int i = 0; i < (int)e.getValue(); i++) {
                sb.append(e.getKey());
            }
        }
        return sb.toString();
    }
}

方法3：

class Solution {
    public String frequencySort(String s) {
        char[] chars = s.toCharArray();
        int[] charsCount = new int[128];
        for (char c: chars) charsCount[c]++;
        
        char[] ret = new char[chars.length];
        int retIndex = 0;
        while (retIndex < ret.length) {
            int maxCount = 0;
            char maxChar = 0;
            
            //find maximum frequency, and set it to be 0 at the end
            for (int i = 0; i < 128; i++) {
                if (charsCount[i] > maxCount) {
                    maxCount = charsCount[i];
                    maxChar = (char) i;
                }
            }
            charsCount[maxChar] = 0;
            
            //build result
            while (maxCount-- > 0) ret[retIndex++] = maxChar;
        }
        return new String(ret);
    }
}