欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

451. Sort Characters By Frequency

程序员文章站 2022-06-03 08:33:12
...

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.

方法1: sort

Complexity

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

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> hash;
        for (char c: s) hash[c]++;
        auto cmp = [&](const char & a, const char & b) {
            if (hash[a] == hash[b]) return a < b;
            return hash[a] > hash[b];
        };
        sort(s.begin(), s.end(), cmp);
        return s;
    }
};

方法1: hash + heap

思路:

这里用到的本质算法是counting sort,主要因为必须保证相同字符连续输出。定义cmp 的方法stable不stable都无法解决这个问题。(可以解决!在词频一致的情况下按照lexicographic order比较,上面的方法) 。

Complexity

Time complexity: O(n),下面证明heapify是o(n), tighter bound than O(n log n)
Space complexity: O(n)
451. Sort Characters By Frequency

class Solution {
public:
    string frequencySort(string s) {
        string res;
        unordered_map<char, int> hash;
        priority_queue<pair<int, char>> pq;
        for (char c: s) hash[c]++;
        for (auto item: hash) pq.push({item.second, item.first});
        while (!pq.empty()) {
            auto top = pq.top();
            pq.pop();
            
            res += string(top.first, top.second);
        }
        return res;
    }
};
相关标签: hash heap