肇庆微网站,wordpress 动态插件,网站建设费摊销几年,关键词全网搜索根据字符出现频率排序
https://leetcode.cn/problems/sort-characters-by-frequency/
描述
给定一个字符串 s #xff0c;根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。返回 已排序的字符串 。如果有多个答案#xff0c;返回其…根据字符出现频率排序
https://leetcode.cn/problems/sort-characters-by-frequency/
描述
给定一个字符串 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 * 1 0 5 10^5 105s 由大小写英文字母和数字组成
算法实现
1 普通方法实现, 基于原生sort和Map结构
function frequencySort(s: string): string {// 1. 构建map字典例如: Map{a: 2, b: 3}const map new Map();s.split().forEach(item {map.set(item, map.has(item) ? map.get(item) 1 : 1);});// 2. 将map转成二维数组进行排序const arr Array.from(map);arr.sort((a, b) b[1] - a[1]);// 3. 基于排好序的数组(降序)组装成最终结果let result ;arr.forEach((item) {result item[0].repeat(item[1]);})return result;
};这里使用平时最简单的原生排序法结合Map数据结构的特性和ES6中字符串的特性完成原生排序性能不错 O(nlogn)推荐
2 使用堆排序
class MaxHeap {map: Mapstring, number new Map()heap: number[] []init(str:string) {// 构建map字典const { map } this;str.split().forEach(item {map.set(item, map.has(item) ? map.get(item) 1 : 1);});this.heap Array.from(map.values());}sort () {const iArr this.heap;const n iArr.length;if (n 1) return iArr;for (let i Math.floor(n / 2); i 0; i--) {MaxHeap.maxHeapify(iArr, i, n);}for (let j 0; j n; j) {MaxHeap.swap(iArr, 0, n - 1 - j);MaxHeap.maxHeapify(iArr, 0, n - 1 - j - 1);}return iArr;}// 排序并转成字符串sortToString () {const arr this.sort(); // 这里对值进行排序const str [];while (arr.length) {const top arr.pop();for (const [k, v] of this.map) {// 值和值匹配if (v top) {str.push(k.repeat(v));this.map.delete(k); // 使用过的key防止重复匹配 这里记得删除break}}}return str.join();}// 交换两个元素static swap (arr, i, j) {if (i j) return;[arr[i], arr[j]] [arr[j], arr[i]];}// 构建最大堆的过程static maxHeapify (Arr, i, size) {// 左节点索引const l (i 1) 1;// 右节点const r (i 1) 2;let largest i;// 父节点i和左节点l做比较取最大if (l size Arr[l] Arr[largest]) largest l;// 右节点和最大值比较if (r size Arr[r] Arr[largest]) largest r;if (largest ! i) {MaxHeap.swap(Arr, i, largest);MaxHeap.maxHeapify(Arr, largest, size);}}
}function frequencySort(s: string): string {const mh new MaxHeap();mh.init(s);return mh.sortToString();
}如果这个堆之前构建好只需要少许修改即可投入使用理解了最大堆的构建过程这个还是比较推荐使用的需要注意的是在while和for的嵌套循环中的时间复杂度的考量 while是每次pop从n直到为0因此是 nfor不会每次都执行n次匹配到时会被break掉因此是 logn所以整体时间复杂度为 O(nlogn)
