当前位置: 代码迷 >> 综合 >> [LeetCode] Sort Characters by Frequency
  详细解决方案

[LeetCode] Sort Characters by Frequency

热度:23   发布时间:2023-12-22 05:38:12.0

https://leetcode.com/problems/sort-characters-by-frequency/?tab=Description

思路1: Priority Queue

  1. 先把所有字符的出现次数统计一下----O(n)
  2. 然后把 (字符, 出现次数) 做成一个node推入优先队列,按题目要求重载比较规则----O(n log n)
  3. 最后依次pop队列元素,构造结果----O(n)

Time complexity: O(n log n)
Space complexity: O(n)

struct Node {char c;int cnt;Node(char _c = '0', int _cnt = 0) : c(_c), cnt(_cnt) {}bool operator< (const Node &other) const {return this->cnt < other.cnt ||(this->cnt == other.cnt && this->c < other.c);} };class Solution { public:string frequencySort(string s) {if (s.empty()) return "";unordered_map<char, int> hash_map;for (char c : s) {hash_map[c]++;}priority_queue<Node> q;string ret = "";for (char c : s) {q.push(Node(c, hash_map[c]));}while (!q.empty()) {ret.push_back(q.top().c);q.pop();}return ret;} };

思路2:

其实大想法还是一样的,就是想办法把(出现次数,字符)按出现次数为首要比较准则构造出来,前面的方法是用Priority Queue / Max Heap。借用counting sort的思想,可以开一个存放字符的数组,如下:

1 2 3 ... n
出现1次的字符 出现2次的字符 出现3次的字符 ... 出现n次的字符

统计好每个字符的出现次数后,就可以填这个表了,填好这个表之后,从后往前扫描一遍就能构造出结果了。有个问题须要注意,可能多个不同的字符出现的次数相等,所以这个表应该设计成存放字符串而不是单个字符的表。

Time complexity: O(n)
Space complexity: O(n) ---严格的O(n)

class Solution { public:string frequencySort(string s) {if (s.empty()) return "";unordered_map<char, int> cnt;for (auto c : s) {cnt[c]++;}vector<string> charof(s.size() + 1);for (const auto& kv : cnt) {charof[kv.second].append(kv.second, kv.first);}string ret = "";for (int i = charof.size() - 1; i >= 1; --i) {if (!charof[i].empty()) {ret.append(charof[i]);}}return ret;} };

个人认为这个方法其实并不多好,在字符串很长时会有较大的空间浪费,比如考虑一个极端情况:一个长度为100万+1的字符串只有两个字符构成:"aaaaa...ab",字符a出现了100万次,字符b出现了1次,这个表就只有第1和第(n-1)的位置放了东西,其他地方都浪费了,如果再算上构造结果的复杂度,在我看来时间是不止O(n)的...

所以在这种情况下,把数组换成Map / Tree Map是比较好的做法,可以有效避免空间浪费,且具有排序的功能(C++ std::map内部是一颗红黑树),最后构造结果的时候从map的最大key开始遍历就可以了:

string frequencySort(string s) {if (s.empty()) return "";unordered_map<char, int> cnt;for (auto c : s) {cnt[c]++;}map<int, string> charof;for (const auto& kv : cnt) {charof[kv.second].append(kv.second, kv.first);}string ret = "";for (auto it = charof.rbegin(); it != charof.rend(); ++it) {ret.append(it->second);}return ret; }

map的插入是O(logn),所以时间复杂度是O(n logn),但是个人认为在字符串长度很长的情况下性能不比上面的做法差。

转载于:https://www.cnblogs.com/ilovezyg/p/6481748.html

  相关解决方案