根据字符出现频率排序(Leetcode 451)

发表于 | 分类于 ， ， ， | | 本文总阅读数 次
| 字数统计: 1.7k | 阅读时长 ≈ 7
Leetcode 451

1

题目分析

   这是TopK类型的题目，经典的求解方法是使用大顶堆进行求解，这也是必须要掌握的一种算法，除此之外介绍另一种基于哈希表的算法。

排序+哈希表

本题要对字符串按照出现的频率进行排序，将出现频率高的字符放在字符串前方，因此我们首先要统计出每个字符串出现的次数，这里使用charToFrequency哈希表记录。然后要统计出现次数对应的字符种类，对出现次数进行从大到小排序即可。如”tree”这个字符串，出现2次的有e，出现1次的有t和r，这里使用frequencyToChar记录，其中键为出现的次数，值为一个可变列表，每个元素都是一个字符。将frequency的键k都存入数组中，表示存在某些字符出现次数为k，对数字从大到小排序，本例中数组为[2, 1]，最后作为键从frequencyToChar中取出相应的列表。先取出frequencyToChar[2]对应的列表[e]，然后再取出frequencyToChar[1]对应的列表[t, r]。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**，其中字符的种类为常数量级，因此不将其放入时间复杂度的计算中

下面是C++语言的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> charToFrequency;
        for (char c : s) { charToFrequency[c]++; }
        map<int, vector<char>> frequencyToChar;
        for (auto& p : charToFrequency) { frequencyToChar[p.second].push_back(p.first); }
        string res = "";
        for (auto& p : frequencyToChar) {
            for (char c : p.second) {
                for (int i = 0; i < p.first; i++) {
                    res.push_back(c);
                }
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

下面是Java语言的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public String frequencySort(String s) {
        HashMap<Character, Integer> charToFrequency = new HashMap<>();
        for (char c : s.toCharArray()) { charToFrequency.put(c, charToFrequency.getOrDefault(c, 0) + 1); }
        TreeMap<Integer, ArrayList<Character>> frequencyToChar = new TreeMap<>((o1, o2) -> o2 - o1);
        for (Map.Entry<Character, Integer> p : charToFrequency.entrySet()) {
            ArrayList<Character> lst = frequencyToChar.getOrDefault(p.getValue(), new ArrayList<>());
            lst.add(p.getKey());
            frequencyToChar.put(p.getValue(), lst);
        }
        StringBuilder res = new StringBuilder();
        for (int f : frequencyToChar.keySet()) {
            for (char c : frequencyToChar.get(f)) {
                res.append(String.valueOf(c).repeat(Math.max(0, f)));
            }
        }
        return res.toString();
    }
}

下面是Python语言的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def frequencySort(self, s):
        char_to_frequency = Counter(s)
        frequency_to_char = {}
        for (c, i) in char_to_frequency.items():
            lst = frequency_to_char.setdefault(i, [])
            lst.append(c)
        res = ""
        sort_list = sorted(frequency_to_char.keys(), key=lambda x: -x)
        for f in sort_list:
            for c in frequency_to_char[f]:
                res += f * c
        return res

下面是Kotlin语言的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    fun frequencySort(s: String): String {
        val charToFrequency = HashMap<Char, Int>()
        for (c in s) { charToFrequency[c] = (charToFrequency[c] ?: 0) + 1 }
        val frequencyToChar = TreeMap<Int, ArrayList<Char>>(Comparator { o1, o2 -> o2 - o1; })
        for (p in charToFrequency) {
            val lst = frequencyToChar.getOrDefault(p.value, ArrayList())
            lst.add(p.key)
            frequencyToChar[p.value] = lst
        }
        val res = StringBuilder()
        for ((f, lst) in frequencyToChar) {
            for (c in lst) {
                res.append(c.toString().repeat(f))
            }
        }
        return res.toString()
    }
}

将四种语言放在一起对比，发现C++语言在操作哈希表时可以不用先判断是否存在键是否存在，其他语言都需要先进行判断。而且在操作字符串时，Python可以进行加法和乘法操作，Java和Kotlin推荐使用StringBuilder和append实现字符串相加的操作，然后使用repeat达到字符串相乘的操作，需要注意的是Java将字符转换为字符串可以使用String的静态方法valueOf(char c)或者Character的静态方法toString(char c)。而Kotlin使用Char对象的成员方法toString()转换为字符串，或者使用字符串模板转换为字符串”$c”。在C++中，使用push_back(char c)添加字符，使用append(string s)添加字符串。如果要达到相乘操作，需要自己写循环，使用append添加字符串。还值得注意的是在C++中map、Java和Kotlin中的TreeMap是有序的，因此对key不需要排序，Python中dict是无序的，因此要进行排序操作。

堆+哈希表

本题要对字符串按照出现的频率进行排序，将出现频率高的字符放在字符串前方，因此我们首先要统计出每个字符串出现的次数，这里使用charToFrequency哈希表记录。然后将{f, c}放入大顶堆中，其中c代表字符串，f代表出现的次数，在大顶堆中，会将字符出现次数最多的放在堆顶，然后逐渐将其弹出即可。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**，其中字符的种类为常数量级，因此不将其放入时间复杂度的计算中

下面是C++语言的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> charToFrequency;
        for (char c : s) { charToFrequency[c]++; }
        string res = "";
        priority_queue<pair<int, char>> heap;
        for (auto& p : charToFrequency) { heap.push({ p.second, p.first }); }
        while (!heap.empty()) {
            auto& cur = heap.top();
            res.append(string(cur.first, cur.second));
            heap.pop();
        }
        return res;
    }
};

下面是Java语言的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String frequencySort(String s) {
        HashMap<Character, Integer> charToFrequency = new HashMap<>();
        for (char c : s.toCharArray()) { charToFrequency.put(c, charToFrequency.getOrDefault(c, 0) + 1); }
        PriorityQueue<Character> heap = new PriorityQueue<>((o1, o2) -> charToFrequency.get(o2) - charToFrequency.get(o1));
        heap.addAll(charToFrequency.keySet());
        StringBuilder res = new StringBuilder();
        while (!heap.isEmpty()) {
            char cur = heap.remove();
            res.append(String.valueOf(cur).repeat(charToFrequency.get(cur)));
        }
        return res.toString();
    }
}

下面是Python语言的题解

1
2
3
4
5
6
7
8
9
10
class Solution:
    def frequencySort(self, s):
        char_to_frequency = Counter(s)
        heap = [[y, x] for x, y in char_to_frequency.items()]
        heapq.heapify(heap)
        res = ""
        while heap:
            cur = heapq.heappop(heap)
            res = cur[0] * cur[1] + res
        return res

下面是Kotlin语言的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    fun frequencySort(s: String): String {
        val charToFrequency = HashMap<Char, Int>()
        for (c in s) { charToFrequency[c] = (charToFrequency[c] ?: 0) + 1 }
        val heap = PriorityQueue<Char>(Comparator { c1, c2 -> charToFrequency[c2]!! - charToFrequency[c1]!! })
        heap.addAll(charToFrequency.keys);
        val res = StringBuilder()
        while (heap.isNotEmpty()) {
            val cur = heap.remove()
            res.append(cur.toString().repeat(charToFrequency[cur]!!))
        }
        return res.toString()
    }
}

将四种语言放在一起对比，发现C++语言的pair可以比较大小，否则要自定义类或结构，重写operator()函数，而且priority_queue默认为最大堆。Java和Kotlin语言要重写Comparator，而且默认为最小堆，Python中heap也是默认最小堆，而且Python中的list和tuple也可以比较大小，否则也要自定义类，重写__lt__比较函数。

刷题总结

  本题非常重要，使用到了自定义类型的堆和哈希操作，因为在实际的工作和开发过程中，往往需要自定义一些类型，因此小伙伴一定要掌握如何使用数据结构对自定义对象进行操作的方法

-------------本文结束感谢您的阅读-------------
0%