前端算法之堆 -- 计数排序

2024-01-06 03:44

本文主要是介绍前端算法之堆 -- 计数排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  • 堆用于解决什么问题
    • 堆排序(Heap Sort):
    • 优先队列(Priority Queue):
    • 图算法中的最短路径和最小生成树问题:
    • 中位数查找:
    • 合并K个有序数组:
  • 例子:库存管理 III On时间复杂度
    • 原生API
    • 使用堆 : 计数排序 – 拿空间换时间
  • 扩展1:JavaScript slice 方法
  • 扩展2:计数排序

堆可以分为 最小堆最大堆 两种类型。

在最小堆中,每个父节点的值都要小于或等于其子节点的值,也就是说,根节点是整个堆中的最小值。

而在最大堆中,每个父节点的值都要大于或等于其子节点的值,也就是说,根节点是整个堆中的最大值。

下面举例说明堆的概念:

最小堆:

假设我们有一个包含以下元素的最小堆:[5, 7, 10, 12, 15, 17, 20]

它的二叉树表示如下:

         5/   \7      10/  \    /  \12   15  17  20

在最小堆中,根节点的值5是整个堆中的最小值。并且,每个父节点的值都小于或等于其子节点的值。

最大堆:

假设我们有一个包含以下元素的最大堆:[30, 25, 20, 15, 10, 5]

它的二叉树表示如下:

        30/   \25      20/   \    /15    10  5

在最大堆中,根节点的值30是整个堆中的最大值。并且,每个父节点的值都大于或等于其子节点的值。

堆可以应用于许多算法和数据结构,例如堆排序、优先队列等。

更多详细内容,请微信搜索“前端爱好者戳我 查看

堆用于解决什么问题

堆(Heap)数据结构可以用于解决以下问题:

堆排序(Heap Sort):

通过使用堆进行排序,可以将一个无序数组转换为有序数组。堆排序的时间复杂度为O(nlogn),是一种高效的排序算法。

优先队列(Priority Queue):

优先队列是一种特殊的队列,每个元素都有与之关联的优先级。堆可以实现优先队列的基本操作,如插入元素、删除具有最高优先级的元素等。常见的应用包括任务调度、事件处理等。

图算法中的最短路径和最小生成树问题:

在一些图算法中,如Dijkstra算法和Prim算法,需要找到最短路径或最小生成树。

堆可以用来维护待处理节点集合,并在每次选择下一个节点时选择具有最小权重的节点。

中位数查找:

在一系列数字中找到中位数是一种常见的问题。使用堆,可以高效地找到中位数,其中最小堆和最大堆可以分别存储较大和较小的一半数字。

合并K个有序数组:

当需要合并多个有序数组时,可以使用堆来提高效率。通过将每个数组的最小元素放入堆中,然后每次弹出堆顶元素进行合并,可以在时间复杂度为O(nlogk)的情况下完成合并操作。

这些只是堆应用的一些例子,堆还可以用于解决其他许多问题,特别是那些需要高效地查找最小或最大元素的场景。

例子:库存管理 III O(n)时间复杂度

原生API

leetcode链接 :https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/

仓库管理员以数组 stock 形式记录商品库存表,其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量,返回 顺序不限。

示例 1:

输入:stock = [2,5,7,4], cnt = 1
输出:[2]

示例 2:

输入:stock = [0,2,3,6], cnt = 2
输出:[0,2][2,0]

提示:

0 <= cnt <= stock.length <= 100000 <= stock[i] <= 10000

思路:先排序,然后取值

/*** @param {number[]} stock* @param {number} cnt* @return {number[]}*/
var inventoryManagement = function(stock, cnt) {// 先排序,然后取值return stock.sort((a,b)=>a-b).slice(0,cnt)
};

使用堆 : 计数排序 – 拿空间换时间

/*** @param {number[]} stock* @param {number} cnt* @return {number[]}*/
var inventoryManagement = function(stock, cnt) {// 先排序,然后取值return  countingSort(stock,cnt,10000)
};const countingSort = (arr,k,length)=>{// 将新开辟一个空间,将输入的数据存储到空间let bucket = new Array(length) let sortedIndex = 0let arrLen = arr.lengthlet bukectLength = length// stock [2,5,7,4] 原抬款组中下标对应的值 对应此处的下标for(let i = 0; i < arrLen;i++){if(!bucket[arr[i]]){bucket[arr[i]]= 0}bucket[arr[i]] ++} // bucket [0,0,1,0,1,1,0,1,]let res = [] for (let j = 0; j < bukectLength;j++){while(bucket[j]-- > 0 && sortedIndex < k){res[sortedIndex++] = j}if(sortedIndex === k){break}}return res
}

扩展1:JavaScript slice 方法

在JavaScript中,slice()是一个数组方法,用于从原始数组中提取指定范围的元素,并返回一个新的数组。它不会修改原始数组,而是返回一个浅拷贝。

slice()方法接受两个参数:起始索引和结束索引(可选)。起始索引指定了截取的起始位置,包含该索引对应的元素;结束索引指定了截取的结束位置,但不包含该索引对应的元素。

使用示例:

const fruits = ['apple', 'banana', 'orange', 'grapefruit', 'kiwi'];// 截取索引1到3之间的元素(不包括索引3)
const slicedFruits = fruits.slice(1, 3);
console.log(slicedFruits); // 输出: ['banana', 'orange']// 不传递结束索引,则截取从起始索引到数组末尾的所有元素
const slicedFruits2 = fruits.slice(2);
console.log(slicedFruits2); // 输出: ['orange', 'grapefruit', 'kiwi']// 负数索引表示从数组末尾开始计算,-2表示倒数第二个元素
const slicedFruits3 = fruits.slice(-2);
console.log(slicedFruits3); // 输出: ['grapefruit', 'kiwi']// 可以将slice()用于字符串
const str = "Hello, World!";
const slicedStr = str.slice(7, 12);
console.log(slicedStr); // 输出: "World"

注意事项:

  • 如果结束索引小于起始索引,则返回一个空数组。
  • 原始数组的元素不会受到slice()方法影响,它仅返回一个新的数组副本。
  • slice()方法对字符串同样适用,可以截取指定范围内的字符子串。

扩展2:计数排序

计数排序(Counting Sort)是一种线性时间复杂度(O(n+k))的排序算法,其中n是待排序元素的数量,k是待排序元素的取值范围大小。计数排序适用于排序范围较小的整数数组。

计数排序的基本思想是统计每个元素出现的次数,然后根据统计信息将元素放回正确的位置。它使用一个额外的计数数组来存储每个元素的出现次数,然后通过累加计数数组中的值,确定每个元素在排好序的数组中的最终位置。

下面是计数排序的示例步骤:

  1. 统计每个元素出现的次数:遍历待排序数组,对每个元素进行计数,并将计数结果存储在对应索引位置的计数数组中。

  2. 累加计数数组:对计数数组进行累加操作,每个位置的值等于前面所有位置的值之和,这样可以确定每个元素在排序后数组中的最终位置。

  3. 排序:创建一个与待排序数组相同大小的临时数组,遍历待排序数组,根据计数数组中的值确定每个元素在临时数组中的位置,并将元素放置到临时数组中。

  4. 将临时数组中的元素复制回原始数组:将临时数组中的元素按顺序复制回原始数组,即完成排序。

以下是一个计数排序的示例代码(使用JavaScript):

function countingSort(arr) {const len = arr.length;if (len <= 1) {return arr;}// 找出待排序数组中的最大值let max = arr[0];for (let i = 1; i < len; i++) {if (arr[i] > max) {max = arr[i];}}// 创建计数数组,并统计每个元素的出现次数const countArray = new Array(max + 1).fill(0);for (let i = 0; i < len; i++) {countArray[arr[i]]++;}// 累加计数数组for (let i = 1; i <= max; i++) {countArray[i] += countArray[i - 1];}// 创建临时数组存储排序结果const tempArray = new Array(len);// 排序for (let i = len - 1; i >= 0; i--) {const value = arr[i];const index = countArray[value] - 1;tempArray[index] = value;countArray[value]--;}// 将临时数组复制回原始数组for (let i = 0; i < len; i++) {arr[i] = tempArray[i];}return arr;
}// 使用示例
const array = [5, 8, 2, 1, 9, 3, 5];
const sortedArray = countingSort(array);
console.log(sortedArray); // 输出: [1, 2, 3, 5, 5, 8, 9]

计数排序的优势在于它不是基于比较的排序算法,因此在某些情况下,它可以比其他排序算法更快。但是,计数排序的缺点是它对输入数据的取值范围有一定要求,并且需要额外的空间来存储计数数组和临时数组。

这篇关于前端算法之堆 -- 计数排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

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

Vue中组件之间传值的六种方式(完整版)

《Vue中组件之间传值的六种方式(完整版)》组件是vue.js最强大的功能之一,而组件实例的作用域是相互独立的,这就意味着不同组件之间的数据无法相互引用,针对不同的使用场景,如何选择行之有效的通信方式... 目录前言方法一、props/$emit1.父组件向子组件传值2.子组件向父组件传值(通过事件形式)方

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

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

css中的 vertical-align与line-height作用详解

《css中的vertical-align与line-height作用详解》:本文主要介绍了CSS中的`vertical-align`和`line-height`属性,包括它们的作用、适用元素、属性值、常见使用场景、常见问题及解决方案,详细内容请阅读本文,希望能对你有所帮助... 目录vertical-ali

浅析CSS 中z - index属性的作用及在什么情况下会失效

《浅析CSS中z-index属性的作用及在什么情况下会失效》z-index属性用于控制元素的堆叠顺序,值越大,元素越显示在上层,它需要元素具有定位属性(如relative、absolute、fi... 目录1. z-index 属性的作用2. z-index 失效的情况2.1 元素没有定位属性2.2 元素处

Python实现html转png的完美方案介绍

《Python实现html转png的完美方案介绍》这篇文章主要为大家详细介绍了如何使用Python实现html转png功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 1.增强稳定性与错误处理建议使用三层异常捕获结构:try: with sync_playwright(

Vue 调用摄像头扫描条码功能实现代码

《Vue调用摄像头扫描条码功能实现代码》本文介绍了如何使用Vue.js和jsQR库来实现调用摄像头并扫描条码的功能,通过安装依赖、获取摄像头视频流、解析条码等步骤,实现了从开始扫描到停止扫描的完整流... 目录实现步骤:代码实现1. 安装依赖2. vue 页面代码功能说明注意事项以下是一个基于 Vue.js

CSS @media print 使用详解

《CSS@mediaprint使用详解》:本文主要介绍了CSS中的打印媒体查询@mediaprint包括基本语法、常见使用场景和代码示例,如隐藏非必要元素、调整字体和颜色、处理链接的URL显示、分页控制、调整边距和背景等,还提供了测试方法和关键注意事项,并分享了进阶技巧,详细内容请阅读本文,希望能对你有所帮助...

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

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

Nginx实现前端灰度发布

《Nginx实现前端灰度发布》灰度发布是一种重要的策略,它允许我们在不影响所有用户的情况下,逐步推出新功能或更新,通过灰度发布,我们可以测试新版本的稳定性和性能,下面就来介绍一下前端灰度发布的使用,感... 目录前言一、基于权重的流量分配二、基于 Cookie 的分流三、基于请求头的分流四、基于请求参数的分