算法-堆/归并排序-排序链表
算法-堆/归并排序-排序链表
1 题目概述
1.1 题目出处
https://leetcode.cn/problems/sort-list/description/?envType=study-plan-v2&envId=top-interview-150
1.2 题目描述


2 优先级队列构建大顶堆
2.1 思路
- 优先级队列构建小顶堆
- 链表所有元素放入小顶堆
- 依次取出堆顶元素,链表串起来即可
2.2 代码
class Solution {public ListNode sortList(ListNode head) {if (head == null) {return null;}PriorityQueue<ListNode> minHeap = new PriorityQueue<>((n1,n2)->n1.val-n2.val);ListNode newHead = new ListNode();while(null != head) {minHeap.add(head);head = head.next;}ListNode tmp = minHeap.poll();tmp.next = null;newHead.next = tmp;while(minHeap.size()>0) {ListNode cur = minHeap.poll();tmp.next = cur;tmp = cur;tmp.next = null;}return newHead.next;}
}
2.3 时间复杂度
O(nlogn)

2.4 空间复杂度
O(n)
3 归并排序
3.1 思路
- 用快慢指针法,找到链表中间位置
- 将链表拆分成两条子链表
- 对子链表分别排序
- 将排序后的子链表合并排序
3.2 代码
class Solution {public ListNode sortList(ListNode head) {if (null == head) {return null;}if (null == head.next) {return head;}ListNode fast = head.next;ListNode slow = head;// 找到fast到中间位置while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}// 切断两个链表fast = slow.next;slow.next = null;// 分别对两个子链表排序slow = sortList(head);fast = sortList(fast);ListNode dummy = new ListNode();head = dummy;// 合并已排序的两个子链表while (null != slow && null != fast) {if (slow.val <= fast.val) {head.next = slow;slow = slow.next;} else {head.next = fast;fast = fast.next;}head = head.next;}while (null != slow) {head.next = slow;slow = slow.next;head = head.next;}while (null != fast) {head.next = fast;fast = fast.next;head = head.next;}return dummy.next;}
}
3.3 时间复杂度

O(nlogn)
3.4 空间复杂度
O(logn)调用栈深度
4 非递归方式(循环)
4.1 思路
3中使用递归方式,空间复杂度O(logn),可改为循环方式达到O(1)的空间复杂度
4.2 代码
4.3 时间复杂度
4.4 空间复杂度
参考文档
- Sort List (归并排序链表)
相关文章:
算法-堆/归并排序-排序链表
算法-堆/归并排序-排序链表 1 题目概述 1.1 题目出处 https://leetcode.cn/problems/sort-list/description/?envTypestudy-plan-v2&envIdtop-interview-150 1.2 题目描述 2 优先级队列构建大顶堆 2.1 思路 优先级队列构建小顶堆链表所有元素放入小顶堆依次取出堆顶…...
word 如何编写4x4矩阵
百度上给的教程,打印出来没有对齐 https://jingyan.baidu.com/article/6b182309995f8dba58e159fc.html 百度上的方式试了一下,不会对齐。导致公式看起来很奇怪。 下面方式会自动对齐 摸索了一下发现可以用下面这种方式编写 4x4 矩阵。先创建一个 3x3…...
INTELlij IDEA编辑VUE项目
菜单中选择setting–>Plugins 或者快捷键 ctrlalts 搜索vue,但有些情况会搜索不出来,先说搜索到的情况 如下图所示: 如果没有vue.js则说明过去已经安装了。 搜索到了后点击Install安装即可, 但即使搜索成功了,也不…...
linux进程间通讯--信号量
1.认识信号量 方便理解:信号量就是一个计数器。当它大于0能用,小于等于0,用不了,这个值自己给。 2.特点: 信号量用于进程间同步,若要在进程间传递数据需要结合共享内存。信号量基于操作系统的 PV 操作&am…...
VS Code连接远程Linux服务器开发c++项目
1.在远程 Linux 上安装包 yum groupinstall "development tools" -y yum install cmake -y2.在 VSCode 上安装插件 C/CC/C Extension PackCMakeCMake ToolsCMake Language Support 3.连接远程Linux服务器...
stable diffusion的模型选择,采样器选择,关键词
一、Stable Diffusion的模型选择: 模型下载地址:https://civitai.com/,需要科学上网。 Deliberate:全能模型,prompt越详细生成的图片质量越好Realistic Vision:现实模型,生成仿真式图片&#…...
BI零售数据分析:以自身视角展开分析
随着零售业务不断扩展,市场竞争不断加剧,各层级的销售管理人员都急需一张能快速查看销售数据分析报表,能从中知道自己管辖内的业务最近或过去的情况,并依次为依据科学优化销售管理措施。这就要求零售数据分析报表信息足够多、数据…...
Maven 使用教程(三)
一、如何使用外部依赖项? 您可能已经注意到POM中的一个dependencies元素,我们一直在使用它作为示例。事实上,您一直在使用外部依赖项,但在这里我们将更详细地讨论它是如何工作的。有关更全面的介绍,请参阅我们的依赖机…...
行秋找工作的记录
2023-10-17 15:35-16:00 中移(苏州)研发中心面试 问了项目,还有一些我没准备到的Java八股文:Java类的加载过程,发射机制,redis存储结构,二叉平衡树等。但我也都没回答上来。应该无了。 2023-1…...
vue项目打包,使用externals抽离公共的第三方库
封装了一个插件,用来vue打包抽离公共的第三方库,使用unplugin进行插件开发,vite对应的功能使用了vite-plugin-externals进行二次开发 github地址 npm地址 hfex-auto-externals-plugin 自动注入插件,使用 unplugin 和 html-webpack-plugin进…...
九阳真经之各大厂校招
大学计算机系的同学要怎么努力才能校招进大厂? 秋招的大公司非常多,也是非常好的,赶上了秋招,你基本工作就敲定了,在整个应届毕业生的人群中你就占据很大的优势了。 如何准备应届校招? 一、做好规划,把…...
Go语言入门心法(五): 函数
Go语言入门心法(一): 基础语法 Go语言入门心法(二): 结构体 Go语言入门心法(三): 接口 Go语言入门心法(四): 异常体系 Go语言入门心法(五): 函数 一: go语言函数认知 函数相关认知升维:函数的功能就是把相对独立的某个相同或者时类型的功能抽象处理,使之成为一个…...
gitignore文件的语法规则
行注释:以"#"符号开头的行表示注释,Git会忽略这些行。空行:空行会被忽略。文件和目录规则: 可以使用通配符来匹配文件和目录。常用的通配符有: “*”:匹配0个或多个字符。“?”:匹配…...
vscode提示扩展主机在过去5分钟内意外终止了3次,解决方法
参考链接: https://code.visualstudio.com/blogs/2021/02/16/extension-bisect https://code.visualstudio.com/docs/setup/uninstall#_clean-uninstall 使用vscode打开jupyter notebook记事本时,窗口右下角提示扩展主机在过去5分钟内意外终止了3次 而…...
【算法挨揍日记】day16——525. 连续数组、1314. 矩阵区域和
525. 连续数组 525. 连续数组 题目描述: 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组,并返回该子数组的长度。 解题思路: 本题的元素只有0和1,根据题目意思,我们可以把题目看成找一段最…...
k8s-13 存储之secret
Secret 对象类型用来保存敏感信息,例如密码、OAuth 令牌和 ssh key。 敏感信息放在 secret 中比放在 Pod 的定义或者容器镜像中来说更加安全和灵活 。 Pod 可以用两种方式使用 secret:作为 volume 中的文件被挂载到 pod 中的一个或者多个容器里 当 kubelet 为 pod 拉…...
什么是高阶成分(HOC)
高阶组件(Higher-Order Component,HOC)是一种在React中用于组件复用和逻辑抽象的设计模式。它本质上是一个函数,接受一个组件作为参数,并返回一个新的组件。 1. HOC的作用: HOC允许我们在不修改原始组件的…...
深度学习硬件配置推荐
目录 1. 基础推荐2. GPU显存与内存是一个1:4的配比?3. deep learning 入门和kaggle比赛4. 有些 Kaggle 比赛数据集很大,可能需要更多的 GPU 显存,请推荐显存4. GDDR6和HBM25. HDD 或 SATA SSD1. 基础推荐 假设您作为一个深度学习入门学者的需求,以下是一份推荐的电脑硬件配…...
数仓建设(一)
想了想,我们的数仓的建设是基于大数据平台进行的,中间也经历了比较曲折的过程。 每个行业都有自身的业务区别,不过很多还是比较相通的。 本文将全面讲解数仓建设规范,从数据模型规范,到数仓公共规范,数仓各…...
Springboot整合taos时序数据库TDengine
1.首先安装TDengine服务端在linux上 TDengine多种安装包的安装和卸载 - TDengine | 涛思数据安装过程直接去官网看,非常详细简单 2.出现的问题 windows连接 invalid app version 版本不对应 版本不对应的问题,需要在linux上安装的版本和windows client版本一致,不然w…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...
GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...
