[LeetCode] 451. Sort Characters By Frequency

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

Example 1:

Input: s = "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: s = "cccaaa"
Output: "aaaccc"
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: s = "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.

Constraints:

• 1 <= s.length <= 5 * 105
• s consists of English letters and digits.

根据字符出现频率排序。

题意是给定一个字符串，请将字符串里的字符按照出现的频率降序排列。注意此题的第三个例子，要求区分大小写。最优解是用到类似桶排序bucket sort的思路，也可以用 priority queue 做但是复杂度高。

首先是桶排序。桶排序的思路用一个 hashmap 记录input里面所有出现过的字符和他们的频率，然后对hashmap（key, value）按照value大小对key重新排序。最后再按照各个字母出现的次数，拼接好最后的字符串。

JavaScript实现

时间O(nlogn) - need to sort the hashmap

空间O(n) - hashmap

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function (s) {
    let map = {};
    for (let letter of s) {
        if (map[letter]) {
            map[letter]++;
        } else {
            map[letter] = 1;
        }
    }

    let res = '';
    let sorted = Object.keys(map).sort((a, b) => map[b] - map[a]);
    for (let letter of sorted) {
        for (let i = 0; i < map[letter]; i++) {
            res += letter;
        }
    }
    return res;
};

Java实现

时间O(n) - no need to sort anything

空间O(n)

class Solution {
    public String frequencySort(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        List<Character>[] bucket = new List[s.length() + 1];
        for (char key : map.keySet()) {
            int freq = map.get(key);
            if (bucket[freq] == null) {
                bucket[freq] = new ArrayList<>();
            }
            bucket[freq].add(key);
        }

        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 = 0; j < map.get(c); j++) {
                        sb.append(c);
                    }
                }
            }
        }
        return sb.toString();
    }
}

其次是用优先队列 priority queue。一开始还是用 hashmap 统计每个不同字母的出现次数，并把整个 map.entry 放入一个以 priority queue 构建的最大堆。堆顶元素是出现次数最多的字母。将每个字母写回 StringBuilder 的时候，我们还是按照出现次数从多到少往回写。

时间O(nlogk)

空间O(n) - priority queue

Java实现

class Solution {
    public String frequencySort(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        PriorityQueue<Map.Entry<Character, Integer>> queue = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        queue.addAll(map.entrySet());

        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            Map.Entry e = queue.poll();
            for (int i = 0; i < (int) e.getValue(); i++) {
                sb.append(e.getKey());
            }
        }
        return sb.toString();
    }
}

bucket sort相关题目

LeetCode 题目总结