LeetCode 451 根据字符出现频率排序 中等

本文主要是介绍LeetCode 451 根据字符出现频率排序 中等，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 451 根据字符出现频率排序 中等

1. 题目详情

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

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

1. 原题链接

LeetCode 451 根据字符出现频率排序 中等

2. 题目要求

示例 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 * 105
s 由大小写英文字母和数字组成

3. 基础框架

● Cpp代码框架

class Solution {
public:string frequencySort(string s) {
};

2. 解题思路

1. 思路分析

$(1)$ 哈希思想，所有可能的字符共有$62$个，开辟一个大小为62的整型数组与每个字符建立唯一映射，整型数组存放每个字符出现的次数;
$(2)$ 题目要求按照出现次数排序字符串，对统计了字符个数的整型数组排序后映射关系将会失效，所以需要新的字符数组记录整型数组对应位置的字符;
$(3)$ 初始化整型数组内容和字符数组内容
$(4)$ 遍历字符串统计字符出现字数并存放在整型数组对应位置;
$(5)$ 同时对整型数组和字符数组排序，字符数组的元素随整型数组的元素移动而移动，这样就保证了排序后整型数组字符出现的次数按降序排列，字符数组元素一一对应整型数组元素；
$(6)$ 依次把字符数组字符尾插到空string对象中，字符在整型数组中出现几次就尾插几次;

2. 时间复杂度

$O(N)$

3. 代码实现

class Solution {
public:string frequencySort(string s) {// 哈希思想映射// 额外字符数组记录整型数组映射的字符int n = 62;int arr1[n];memset(arr1, 0, n * sizeof(int));char arr2[n];// ['a', 'z'] [0, 25]// ['A', 'Z'] [26, 51]// ['0', '9'] [52, 61]for(int i = 0, j = 0; i < n; ++i, ++j){if(i < 26)arr2[i] = 'a' + j;else if(i < 52)arr2[i] = 'A' + j % 26;elsearr2[i] = '0' + j % 52;}// 统计字符串字符出现次数，使用整型数组映射for(auto & e : s){char c;if(islower(e)) arr1[e - 'a']++;else if(isupper(e)) arr1[e - 'A' + 26]++;else arr1[e - '0' + 52]++;}// 按照出现次数对整型数组排序，字符数组随整型数组而排序，保证对应下标位置的字符和出现次数依然对应sorts(arr1, arr2, n);// 遍历按降序排好的整型数组，对应字符数组中的字符顺序就是按照字符出现次序降序排列的// 依次把字符数组字符尾插到空string对象中，出现几次就尾插几次string ret;for(int i = 0; i < n; ++i){for(int j = 0; j < arr1[i]; ++j){ret += arr2[i];}}return ret;}void sorts(int* arr1, char* arr2, int n){for(int i = 0; i < n; ++i){bool flag = true; // 默认有序, 如果真有序就提前结束排序for(int j = 0; j < n - i - 1; ++j){if(arr1[j] < arr1[j + 1]){swap(arr1[j], arr1[j + 1]);swap(arr2[j], arr2[j + 1]);flag = false;}}if(flag) break;}}
};

---

这篇关于LeetCode 451 根据字符出现频率排序 中等的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---