leetcode 451.根据字符出现频率排序

LeetCode第451题“根据字符出现频率排序”要求根据字符串中字符的出现频率对字符串进行排序。可以通过以下步骤解决这个问题：

方法一

1. 使用哈希表统计每个字符的频率。
2. 使用最大堆根据频率对字符进行排序。
3. 根据排序结果构造输出字符串。

下面是C++实现的具体代码：

代码实现

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

class Solution {
public:
    string frequencySort(string s) {
        // 1. 统计每个字符的频率
        unordered_map<char, int> frequencyMap;
        for (char c : s) {
            frequencyMap[c]++;
        }

        // 2. 使用最大堆根据频率排序字符
        priority_queue<pair<int, char>> maxHeap;
        for (auto& entry : frequencyMap) {
            maxHeap.push({entry.second, entry.first});
        }

        // 3. 根据排序结果构造输出字符串
        string result;
        while (!maxHeap.empty()) {
            auto [freq, ch] = maxHeap.top();
            maxHeap.pop();
            result.append(freq, ch);
        }

        return result;
    }
};

int main() {
    Solution solution;
    string s = "tree";
    string result = solution.frequencySort(s);
    cout << "Sorted by frequency: " << result << endl;
    return 0;
}

解释

1. 统计每个字符的频率

unordered_map<char, int> frequencyMap;
for (char c : s) {
    frequencyMap[c]++;
}

• 使用哈希表frequencyMap统计字符串中每个字符的出现频率。

2. 使用最大堆根据频率排序字符

priority_queue<pair<int, char>> maxHeap;
for (auto& entry : frequencyMap) {
    maxHeap.push({entry.second, entry.first});
}

• 使用优先队列maxHeap，其中元素是pair<int, char>，表示字符及其频率。
• 将每个字符及其频率插入最大堆中。

3. 根据排序结果构造输出字符串

string result;
while (!maxHeap.empty()) {
    auto [freq, ch] = maxHeap.top();
    maxHeap.pop();
    result.append(freq, ch);
}

• 从最大堆中依次取出字符及其频率，将字符按频率重复添加到结果字符串中。

总结

这个方法的时间复杂度主要是O(N log N)，其中N是字符串的长度。通过这种方式，可以高效地根据字符出现的频率对字符串进行排序。

方法二

这个实现方法主要通过哈希表统计字符频率，然后使用自定义排序规则对字符串进行排序。具体步骤如下：

1. 使用哈希表统计每个字符的出现频率。
2. 定义一个比较函数，根据字符的频率和字典序对字符进行排序。
3. 使用 std::sort 函数对字符串进行排序。

下面是对这段代码的详细解释：

#include <string>
#include <unordered_map>
#include <algorithm>
using std::unordered_map;
using std::string;
/*
 * @lc app=leetcode.cn id=451 lang=cpp
 *
 * [451] 根据字符出现频率排序
 */

// @lc code=start
class Solution {
public:
    string frequencySort(string s) {
        // 1. 使用哈希表统计每个字符的出现频率
        unordered_map<char, int> dict;  // 哈希表，键为字符，值为该字符的出现频率
        for (auto c : s) {
            dict[c]++;
        }

        // 2. 定义一个比较函数
        auto compare = [&dict](const char& a, const char& b) {
            return (dict[a] > dict[b]) || (dict[a] == dict[b] && (a < b));
        };

        // 3. 使用 std::sort 函数对字符串进行排序
        std::sort(s.begin(), s.end(), compare);

        return s;
    }
};
// @lc code=end

详细解释

1. 统计字符频率：

   unordered_map<char, int> dict;
   for (auto c : s) {
       dict[c]++;
   }
   

   • dict 是一个 unordered_map，用于存储每个字符及其出现的频率。
   • 遍历字符串 s，将每个字符的频率记录到 dict 中。

2. 定义比较函数：

   auto compare = [&dict](const char& a, const char& b) {
       return (dict[a] > dict[b]) || (dict[a] == dict[b] && (a < b));
   };
   

   • compare 是一个 lambda 表达式，用于自定义排序规则。
   • dict[a] > dict[b]：按字符频率从高到低排序。
   • dict[a] == dict[b] && (a < b)：如果频率相同，则按字符的字典序从小到大排序。

3. 排序字符串：

   std::sort(s.begin(), s.end(), compare);
   

   • 使用 std::sort 函数对字符串 s 进行排序。
   • s.begin() 和 s.end() 分别表示字符串的起始迭代器和结束迭代器。
   • compare 函数作为自定义的比较规则。

示例

假设输入字符串为 "tree"：

1. 统计字符频率：

   t: 1
   r: 1
   e: 2
   

2. 自定义比较函数会将字符按频率从高到低排序，如果频率相同，则按字典序排序。

3. 排序后的字符串为 "eert"。

运行效果

这段代码可以正确地根据字符出现的频率对字符串进行排序，满足题目要求。你可以在你的环境中运行这个代码来验证其正确性。

原文地址：https://blog.csdn.net/m0_49013185/article/details/140572236

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！