MENU

LeetCode451. Sort Characters By Frequency(模拟)

2019 年 02 月 15 日 • 阅读: 1349 • LeetCode阅读设置

LeetCode451. Sort Characters By Frequency(模拟)

  • Medium
  • Accepted:81,281
  • Submissions:148,685

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.

链接

https://leetcode.com/problems/sort-characters-by-frequency/

题意

给定一个字符串,按照字符出现的频率从大到到小排序。相同字符相邻,频率相同时不同字符顺序可以不同,区分大小写。

题解

  • 对字符按照出现次数用sort进行排序,时间复杂度$O(nlogn)$
  • 对字符进行“计数排序”,灵活使用vector,将出现次数相同的字符放到一起,再从后往前遍历

代码

  • Runtime: 48 ms, faster than 30.00% of C++ online submissions for Sort Characters By Frequency.
  • Memory Usage: 10.5 MB, less than 100.00% of C++ online submissions for Sort Characters By Frequency.
  • 话说直接写cmp函数会报错(已发现错误:reference to non-static member function must be called
class Solution {
public:
//    int cnt[256] = {0};
//
//    bool cmp(char a, char b)
//    {
//        return cnt[a] > cnt[b] || (cnt[a] == cnt[b] && a < b);
//    }

    string frequencySort(string s) {
        int n = s.length();
        int cnt[256] = {0};
        for (int i = 0; i < n; ++i)
            cnt[s[i]]++;
        // sort(s.begin(), s.end(), cmp); // error
        sort(s.begin(), s.end(), [&](char a, char b) // 高级写法
        {
             return cnt[a] > cnt[b] || (cnt[a] == cnt[b] && a < b);
        });
        return s;
    }
};
  • Runtime: 28 ms, faster than 42.31% of C++ online submissions for Sort Characters By Frequency.
  • Memory Usage: 18.6 MB, less than 100.00% of C++ online submissions for Sort Characters By Frequency.
class Solution {
public:
    string frequencySort(string s) {
        int n = s.length();
        unordered_map <char, int> umap;
        vector <string> vt(n + 1, "");
        string ans;
        for (int i = 0; i < n; ++i) // 统计字符出现次数
            umap[s[i]]++;
        unordered_map <char, int> ::iterator it;
        for (it = umap.begin(); it != umap.end(); ++it) // 次数相同的放到一起
            vt[it->second].append(it->second, it->first);
        for (int i = n; i > 0; --i) // 从后往前遍历
        {
            if (!vt[i].empty())
                ans.append(vt[i]);
        }
        return ans;
    }
};

The end.
2019年2月15日 星期五
最后编辑于: 2019 年 02 月 17 日