数据结构与算法之堆: Leetcode 451. 根据字符出现频率排序 (Typescript版)

本文主要是介绍数据结构与算法之堆: Leetcode 451. 根据字符出现频率排序 (Typescript版),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

根据字符出现频率排序

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

算法实现

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: Map<string, 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,因此是 n
    • for不会每次都执行n次,匹配到时会被break掉,因此是 logn
    • 所以整体时间复杂度为 O(nlogn)

这篇关于数据结构与算法之堆: Leetcode 451. 根据字符出现频率排序 (Typescript版)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/3486

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Android如何获取当前CPU频率和占用率

《Android如何获取当前CPU频率和占用率》最近在优化App的性能,需要获取当前CPU视频频率和占用率,所以本文小编就来和大家总结一下如何在Android中获取当前CPU频率和占用率吧... 最近在优化 App 的性能,需要获取当前 CPU视频频率和占用率,通过查询资料,大致思路如下:目前没有标准的

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

C# string转unicode字符的实现

《C#string转unicode字符的实现》本文主要介绍了C#string转unicode字符的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随... 目录1. 获取字符串中每个字符的 Unicode 值示例代码:输出:2. 将 Unicode 值格式化

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

Rust中的BoxT之堆上的数据与递归类型详解

《Rust中的BoxT之堆上的数据与递归类型详解》本文介绍了Rust中的BoxT类型,包括其在堆与栈之间的内存分配,性能优势,以及如何利用BoxT来实现递归类型和处理大小未知类型,通过BoxT,Rus... 目录1. Box<T> 的基础知识1.1 堆与栈的分工1.2 性能优势2.1 递归类型的问题2.2