根据字符出现频率排序

题目描述

给定一个字符串s，根据字符出现的频率对其进行降序排序。一个字符出现的频率是它出现在字符串中的次数。

返回 已排序的字符串 。如果有多个答案，返回其中任何一个。

示例

示例1

输入: s = "tree"
输出: "eert"
解释: 'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

示例2

输入: s = "cccaaa"
输出: "cccaaa"
解释: 'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。

示例3

输入: s = "Aabb"
输出: "bbAa"
解释: 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。

提示：

• 1 <= s.length <= 5*10^5
• s 由大小写英文字母和数字组成

解题思路

解法1

根据频率排序后重新构建字符串

1. 统计每个字符出现的频率
2. 降序排序
3. 重建字符串

时间复杂度：O(n) 空间复杂度：O(1)

C++ 解法

解法1

#include <string>
#include <vector>
#include <utility>
#include <algorithm>

class Solution {
public:
    string frequencySort(string s)
    {
        // 统计字符出现的频率
        vector<int> freq(128, 0);
        for (char c : s)
            ++freq[c];

        // 转化成vector方便排序
        vector<pair<char, int>> items;
        items.reserve(128);
        for (int c = 0; c < 128; ++c) {
            if (freq[c] > 0) items.emplace_back(static_cast<char>(c), freq[c]);
        }

        // 按照频率降序排序
        ranges::sort(items, [](const auto &a, const auto &b) { return a.second > b.second; });

        // 构造结果字符串
        string res;
        res.reserve(s.size());
        for (auto [c, f] : items) {
            res.append(f, c);
        }
        return res;
    }
};

LeetCode链接： 451. 根据字符出现频率排序