算法-堆/归并排序-排序链表
算法-堆/归并排序-排序链表
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…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
PHP 8.5 即将发布:管道操作符、强力调试
前不久,PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5!作为 PHP 语言的又一次重要迭代,PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是,借助强大的本地开发环境 ServBay&am…...
深入浅出Diffusion模型:从原理到实践的全方位教程
I. 引言:生成式AI的黎明 – Diffusion模型是什么? 近年来,生成式人工智能(Generative AI)领域取得了爆炸性的进展,模型能够根据简单的文本提示创作出逼真的图像、连贯的文本,乃至更多令人惊叹的…...
LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用
中达瑞和自2005年成立以来,一直在光谱成像领域深度钻研和发展,始终致力于研发高性能、高可靠性的光谱成像相机,为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...
第八部分:阶段项目 6:构建 React 前端应用
现在,是时候将你学到的 React 基础知识付诸实践,构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段,你可以先使用模拟数据,或者如果你的后端 API(阶段项目 5)已经搭建好,可以直接连…...
【若依】框架项目部署笔记
参考【SpringBoot】【Vue】项目部署_no main manifest attribute, in springboot-0.0.1-sn-CSDN博客 多一个redis安装 准备工作: 压缩包下载:http://download.redis.io/releases 1. 上传压缩包,并进入压缩包所在目录,解压到目标…...
链式法则中 复合函数的推导路径 多变量“信息传递路径”
非常好,我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题,统一使用 二重复合函数: z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y)) 来全面说明。我们会展示其全微分形式(偏导…...
