Day4 25/2/17 MON

【一周刷爆LeetCode,算法大神左神(左程云)耗时100天打造算法与数据结构基础到高级全家桶教程,直击BTAJ等一线大厂必问算法面试题真题详解(马士兵)】https://www.bilibili.com/video/BV13g41157hK?p=4&vd_source=04ee94ad3f2168d7d5252c857a2bf358

目录

2、认识O(NlogN)的排序

2.3 快排QuickSort

2.3.1 快排1.0

2.3.2 快排2.0

2.3.3 快排3.0

2.4 堆排序

2.4.1 heap-insert过程


笔记:

2、认识O(NlogN)的排序

2.3 快排QuickSort

情况1:给定一个数组arr和一个属num让小于等于num的元素都位于它左侧,大于num的数都在数组右侧。要求额外空间复杂度O(1),时间复杂度O(N)。

解法:arr[i]<=num,arr[i]和L区的下一个交换。L区右扩;arr[i]>num,i++;

情况2:给定一个数组arr和一个属num让小于num的元素都位于它左侧,等于num的数在数组中间,大于num的数都在数组右侧。要求额外空间复杂度O(1)、时间复杂度O(N)。

解法:

arr[i]<num,arr[i]和L区的下一个交换。L区右扩;

arr[i]==num,i++;

arr[i]>num,arr[i]和R区的上一个交换。R区左扩;

2.3.1 快排1.0

取最右侧的数,把它左侧的数分为小于它的左区域和小于它的右区域,然后再把它和右区域的第一个数交换。再分别对左区域和右区域执行相同的操作。

【Q1:分治和递归的区别?

A1:二者是不同维度的概念。递归是程序的实现方式,是程序调用自身;分支是一种算法,核心思想是将父问题拆分为多个无重叠的子问题。逐个解决每类子问题后,合并子问题的解,得到父问题的解。分治可以用递归实现。】

2.3.2 快排2.0

取最右侧的数,将左侧的所有元素按“小于区域”“等于区域”“大于区域”排列,然后再把它和“大于区域”的第一个数做交换。

优于“快排1.0”是因为它固定下来了“等于区域”,移动其他元素时不用再移动这部分。

快排1.0和2.0的时间复杂度都是O(N^2)。性能最好的情况,是左右两侧等规模地不断进行二分,时间复杂度为O(NlogN)。

2.3.3 快排3.0

随机选一个数作为划分参照物,把它和最右侧的元素交换。由于数是随机选的,所以处于每个位置上的概率都相同,为1/N。因此把所有可能的master公式求概率相加后再求数学上的长期期望,得到O(NlogN)。

综合来看,快排3.0由于是随机选数所以时间复杂度最接近O(NlogN)。

2.4 堆排序

把数组转化为完全二叉树的话,一个节点的左孩子是arr[2i+1],右孩子是arr[2i+2],父节点是arr[(i-1)/2]。

堆是完全二叉树,分为大根堆和小根堆。大根堆是在这个完全二叉树中,每一棵子树的根节点都大于树上的所有节点。小根堆反之亦然。

2.4.1 heap-insert过程

若不断有新的数加入,如何维持大根堆:“heap-insert”过程。如果子节点大于父节点,直接交换该节点arr[i]和父节点arr[(i-1)/2],不断和父节点比较,如果父节点比当前节点大或已经抵达了根节点,停止交换。小根堆也相似,不断让比父节点小的值和父节点交换。

如果用户要获取并移除大根堆中的最大值,该怎么维持大根堆:用最新加入的值替换掉最大值(根节点),heapSize-1,先比较再交换,直至变成大根堆。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/19584.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

redis集群模式

1.集群模式 作用&#xff1a;解决单点故障问题 集群的模式&#xff1a;1.主从模式&#xff0c;2、哨兵模式&#xff0c;3、集群化模式 1.1主从模式 特点&#xff1a;1个主节点多个从节点&#xff0c;主节点负责读写操作&#xff0c;而从节点只能负责读操作&#xff0c;当主…

力扣 乘积最大子数组

动态规划&#xff0c;注意负负得正&#xff0c;dp交换。 题目 注意这里的dp的乘积要求最大&#xff0c;而两个很大的负数相乘也是大的&#xff0c;因此在每遍历到一个数时要存一个最大值的dp与一个最小值的dp&#xff0c;然后遍历完后再去存ans的dp。由于存在负数&#xff0c;…

【Postgresql】Windows 部署 Postgresql 数据库 (图文教程)

文章目录 准备工作Postgresql 下载Postgresql 安装初始化数据库数据库链接设置允许远程连接测试链接 更多相关内容可查看 准备工作 操作系统&#xff1a;Windows 7 或更高版本&#xff08;推荐 Windows 10 或 Windows Server 2016&#xff09;。 硬件要求&#xff1a; 至少 …

【ENSP】链路聚合的两种模式

【ENSP】链路聚合的两种模式 1、背景介绍2、链路聚合的使用场景3、配置过程1、手工模式Eth-Trunk配置2、静态LACP模式Eth-Trunk 4、总结 1、背景介绍 随着网络规模的不断扩大&#xff0c;人们对骨干链路的带宽吞吐量和可靠性提出了越来越高的要求。在传统方案中&#xff0c;为…

《深度学习》——调整学习率和保存使用最优模型

调整学习率 在使用 PyTorch 进行深度学习训练时&#xff0c;调整学习率是一个重要的技巧&#xff0c;合适的学习率调整策略可以帮助模型更好地收敛。 PyTorch 提供了多种调整学习率的方法&#xff0c;下面将详细介绍几种常见的学习率调整策略及实例代码&#xff1a; torch.opt…

SpringBoot+微信小程序+数据可视化的宠物到家喂宠服务(程序+论文+讲解+安装+调试+售后等)

感兴趣的可以先收藏起来&#xff0c;还有大家在毕设选题&#xff0c;项目以及论文编写等相关问题都可以给我留言咨询&#xff0c;我会一一回复&#xff0c;希望帮助更多的人。 系统介绍 在经济高速发展、物质生活极大丰富的当下&#xff0c;人们的精神需求愈发凸显&#xff0…

《仙台有树》追剧疑问与DeepSeek解答

本篇形式&#xff1a;直接以两段对话直接呈现&#xff0c;有删减 本篇背景&#xff1a;看过太多逻辑bug&#xff0c;有些bug无药可救直接弃剧&#xff0c;有些bug情有可原包容理解。想到最近大火的DeepSeek&#xff0c;就与时俱进&#xff0c;简单直接点吧&#xff0c;也许自己…

Java版企业电子招标采购系统源业码Spring Cloud + Spring Boot +二次开发+ MybatisPlus + Redis

功能描述 1、门户管理&#xff1a;所有用户可在门户页面查看所有的公告信息及相关的通知信息。主要板块包含&#xff1a;招标公告、非招标公告、系统通知、政策法规。 2、立项管理&#xff1a;企业用户可对需要采购的项目进行立项申请&#xff0c;并提交审批&#xff0c;查看所…

txt文件批量转PDF

需要使用acrobat DC软件。 工具 – 创建 PDF – 多个文件&#xff08;可以选择多个TXT文件&#xff0c;过多可能内存溢出&#xff09;。

学习笔记之debian的thonny开发(尚未验证)--从stm32裸机到linux嵌入式系统

这应该算 stm32裸机用户 转 linux嵌入式系统 的入门学习笔记。 【鲁班猫】39-vnc远程桌面连接鲁班猫_哔哩哔哩_bilibili 本集的鲁班猫的视频介绍中&#xff0c;没有清晰明确指出需要linux开发板接入网络&#xff0c;接入网络可以使用有线网口或者wifi路由&#xff0c;有些提示…

PVE使用一个物理网卡采用VLAN为管理IP和VM分配网络的问题

问题描述&#xff1a; 部署PVE后&#xff0c; 想着在上面部署多个不同VLAN的VM &#xff08;类似于VMwarere ESXi&#xff09;&#xff0c;但有人反馈无法使用VLAN&#xff0c;只能配置部署PVE时使用的网段。 问题分析&#xff1a; 在PVE的主机节点网络配置中&#xff0c;默认…

15.3.10 窗体下使用多线程

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 从.Net FrameWork2.0开始&#xff0c;为了加强了程序安全&#xff0c;防止跨线程调用导致不可预知的结果。微软将窗体主线程&#x…

ASP.NET Core SixLabors.ImageSharp v3.x 的图像实用程序类

使用用 C# 编写的 asp.net core web 应用程序示例在 Windows 和 Linux web 服务器上处理图像&#xff0c;包括创建散点图和直方图&#xff0c;以及根据需要旋转图像以便正确显示。 这个小型实用程序库需要将 NuGet SixLabors.ImageSharp包&#xff08;版本 3.1.x&#xff09;添…

【leetcode】200.岛屿数量(DFS入门)

实战总结 用char型接收整形int转化为的对应字符要小心 int res; char res 0; 其中 res 的上限是127。 在下面这道题中&#xff0c;笔者一开始想将遍历过的位置更新值为 res ‘0’&#xff0c;但当岛屿数过多的时候就溢出了&#xff0c;所以还是应该将遍历过的位置更新为‘…

CES Asia 2025“科技+文旅”融合计划:开启文旅新篇

CES Asia 2025第七届亚洲消费电子技术贸易展&#xff08;赛逸展&#xff09;将在首都北京盛大举行&#xff0c;其亮点十三“‘科技文旅’融合计划”备受瞩目&#xff0c;为科技与文旅产业的深度融合带来了新的契机与活力。 在“科技文旅”融合计划中&#xff0c;景区智能设备租…

【Git版本控制器】第三弹——版本回退,撤销修改,删除文件

&#x1f381;个人主页&#xff1a;我们的五年 &#x1f50d;系列专栏&#xff1a;Linux网络编程 &#x1f337;追光的人&#xff0c;终会万丈光芒 &#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐文章 ​ 相关笔记&#xff1a; https://blog.csdn.net/djd…

DeepSeek ,银行营销会被 AIGC 颠覆吗?

AI 让银行营销更智能&#xff0c;但更重要的是“懂客户” AI 在银行营销中的应用已经不仅仅局限于文案生成&#xff0c;而是渗透到了整个营销流程。 据悉&#xff0c;中国银行已经开始利用 AI 大模型构建智能营销助手系统&#xff0c;结合知识图谱和 AI 技术&#xff0c;实现…

【产品推介】可驱动5A负载的降压型DC/DC转换器XBL1663

一、产品简介 采用ESOP-8封装的XBL1663最大可输出5A电流 芯伯乐XBL1663是一款专为降压型DC/DC转换器设计的单片集成电路&#xff0c;具有高转换效率、恒定开关频率工作的特点。内置功率 MOSFET可在 4.5 V-40V 输入电源上实现 5A 峰值输出电流&#xff0c;并具有出色的负载和线…

Rust编程语言入门教程(四)猜数游戏:一次猜测

目录 引言猜数游戏——目标一、创建项目二、编写代码三、运行代码四、代码解释总结 引言 猜数游戏是一个经典的编程练习&#xff0c;它不仅能够帮助开发者熟悉基本的输入输出操作&#xff0c;还能深入理解条件判断和用户交互的逻辑。在 Rust 中&#xff0c;通过标准库提供的 s…

.NET版PDF处理控件Aspose.PDF教程:在 C# 中将 TIFF 文件转换为 PDF

将TIFF文件转换为PDF文档在各个行业中都是必不可少的。许多企业需要将文档转换为存档、共享或打印。TIFF 文件通常用于图像&#xff0c;而 PDF 是文档共享的标准。将 TIFF 文件转换为 PDF 可确保跨不同平台的兼容性和易用性。在这篇博文中&#xff0c;我们将探讨如何使用 Aspos…