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

2024-01-06 03:44
文章标签 算法 计数 排序 前端 frontend 之堆

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

  • 堆用于解决什么问题
    • 堆排序（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。

相关文章

通俗易懂的Java常见限流算法具体实现

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》：本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1
阅读更多...
spring-boot-starter-thymeleaf加载外部html文件方式

spring-boot-starter-thymeleaf加载外部html文件方式

《spring-boot-starter-thymeleaf加载外部html文件方式》本文介绍了在SpringMVC中使用Thymeleaf模板引擎加载外部HTML文件的方法,以及在SpringBoo... 目录1.Thymeleaf介绍2.springboot使用thymeleaf2.1.引入spring
阅读更多...
部署Vue项目到服务器后404错误的原因及解决方案

部署Vue项目到服务器后404错误的原因及解决方案

《部署Vue项目到服务器后404错误的原因及解决方案》文章介绍了Vue项目部署步骤以及404错误的解决方案,部署步骤包括构建项目、上传文件、配置Web服务器、重启Nginx和访问域名,404错误通常是... 目录一、vue项目部署步骤二、404错误原因及解决方案错误场景原因分析解决方案一、Vue项目部署步骤
阅读更多...
前端原生js实现拖拽排课效果实例

前端原生js实现拖拽排课效果实例

《前端原生js实现拖拽排课效果实例》：本文主要介绍如何实现一个简单的课程表拖拽功能,通过HTML、CSS和JavaScript的配合,我们实现了课程项的拖拽、放置和显示功能,文中通过实例代码介绍的... 目录1. 效果展示2. 效果分析2.1 关键点2.2 实现方法3. 代码实现3.1 html部分3.2
阅读更多...
Spring排序机制之接口与注解的使用方法

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri
阅读更多...
CSS弹性布局常用设置方式

CSS弹性布局常用设置方式

《CSS弹性布局常用设置方式》文章总结了CSS布局与样式的常用属性和技巧,包括视口单位、弹性盒子布局、浮动元素、背景和边框样式、文本和阴影效果、溢出隐藏、定位以及背景渐变等,通过这些技巧,可以实现复杂... 一、单位元素vm 1vm 为视口的1%vh 视口高的1%vmin 参照长边vmax 参照长边re
阅读更多...
CSS3中使用flex和grid实现等高元素布局的示例代码

CSS3中使用flex和grid实现等高元素布局的示例代码

《CSS3中使用flex和grid实现等高元素布局的示例代码》：本文主要介绍了使用CSS3中的Flexbox和Grid布局实现等高元素布局的方法，通过简单的两列实现、每行放置3列以及全部代码的展示，展示了这两种布局方式的实现细节和效果，详细内容请阅读本文，希望能对你有所帮助... 过往的实现方法是使用浮动加
阅读更多...
css渐变色背景|＜gradient示例详解

css渐变色背景|＜gradient示例详解

《css渐变色背景|＜gradient示例详解》CSS渐变是一种从一种颜色平滑过渡到另一种颜色的效果,可以作为元素的背景,它包括线性渐变、径向渐变和锥形渐变，本文介绍css渐变色背景|＜gradien... 使用渐变色作为背景可以直接将渐China编程变色用作元素的背景，可以看做是一种特殊的背景图片。（是作为背
阅读更多...
CSS自定义浏览器滚动条样式完整代码

CSS自定义浏览器滚动条样式完整代码

《CSS自定义浏览器滚动条样式完整代码》：本文主要介绍了如何使用CSS自定义浏览器滚动条的样式，包括隐藏滚动条的角落、设置滚动条的基本样式、轨道样式和滑块样式，并提供了完整的CSS代码示例，通过这些技巧，你可以为你的网站添加个性化的滚动条样式，从而提升用户体验，详细内容请阅读本文，希望能对你有所帮助...
阅读更多...
css实现图片旋转功能

css实现图片旋转功能

《css实现图片旋转功能》：本文主要介绍了四种CSS变换效果：图片旋转90度、水平翻转、垂直翻转，并附带了相应的代码示例，详细内容请阅读本文，希望能对你有所帮助... 一 css实现图片旋转90度.icon{ -moz-transform:rotate(-90deg); -webkit-transfo
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2