当前位置: 首页 > news >正文

算法-堆/归并排序-排序链表

算法-堆/归并排序-排序链表

1 题目概述

1.1 题目出处

https://leetcode.cn/problems/sort-list/description/?envType=study-plan-v2&envId=top-interview-150

1.2 题目描述

在这里插入图片描述
在这里插入图片描述

2 优先级队列构建大顶堆

2.1 思路

  1. 优先级队列构建小顶堆
  2. 链表所有元素放入小顶堆
  3. 依次取出堆顶元素,链表串起来即可

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 思路

  1. 用快慢指针法,找到链表中间位置
  2. 将链表拆分成两条子链表
  3. 对子链表分别排序
  4. 将排序后的子链表合并排序

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矩阵

百度上给的教程&#xff0c;打印出来没有对齐 https://jingyan.baidu.com/article/6b182309995f8dba58e159fc.html 百度上的方式试了一下&#xff0c;不会对齐。导致公式看起来很奇怪。 下面方式会自动对齐 摸索了一下发现可以用下面这种方式编写 4x4 矩阵。先创建一个 3x3…...

INTELlij IDEA编辑VUE项目

菜单中选择setting–>Plugins 或者快捷键 ctrlalts 搜索vue&#xff0c;但有些情况会搜索不出来&#xff0c;先说搜索到的情况 如下图所示&#xff1a; 如果没有vue.js则说明过去已经安装了。 搜索到了后点击Install安装即可&#xff0c; 但即使搜索成功了&#xff0c;也不…...

linux进程间通讯--信号量

1.认识信号量 方便理解&#xff1a;信号量就是一个计数器。当它大于0能用&#xff0c;小于等于0&#xff0c;用不了&#xff0c;这个值自己给。 2.特点&#xff1a; 信号量用于进程间同步&#xff0c;若要在进程间传递数据需要结合共享内存。信号量基于操作系统的 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的模型选择&#xff1a; 模型下载地址&#xff1a;https://civitai.com/&#xff0c;需要科学上网。 Deliberate&#xff1a;全能模型&#xff0c;prompt越详细生成的图片质量越好Realistic Vision&#xff1a;现实模型&#xff0c;生成仿真式图片&#…...

BI零售数据分析:以自身视角展开分析

随着零售业务不断扩展&#xff0c;市场竞争不断加剧&#xff0c;各层级的销售管理人员都急需一张能快速查看销售数据分析报表&#xff0c;能从中知道自己管辖内的业务最近或过去的情况&#xff0c;并依次为依据科学优化销售管理措施。这就要求零售数据分析报表信息足够多、数据…...

Maven 使用教程(三)

一、如何使用外部依赖项&#xff1f; 您可能已经注意到POM中的一个dependencies元素&#xff0c;我们一直在使用它作为示例。事实上&#xff0c;您一直在使用外部依赖项&#xff0c;但在这里我们将更详细地讨论它是如何工作的。有关更全面的介绍&#xff0c;请参阅我们的依赖机…...

行秋找工作的记录

2023-10-17 15:35-16:00 中移&#xff08;苏州&#xff09;研发中心面试 问了项目&#xff0c;还有一些我没准备到的Java八股文&#xff1a;Java类的加载过程&#xff0c;发射机制&#xff0c;redis存储结构&#xff0c;二叉平衡树等。但我也都没回答上来。应该无了。 2023-1…...

vue项目打包,使用externals抽离公共的第三方库

封装了一个插件&#xff0c;用来vue打包抽离公共的第三方库&#xff0c;使用unplugin进行插件开发&#xff0c;vite对应的功能使用了vite-plugin-externals进行二次开发 github地址 npm地址 hfex-auto-externals-plugin 自动注入插件,使用 unplugin 和 html-webpack-plugin进…...

九阳真经之各大厂校招

大学计算机系的同学要怎么努力才能校招进大厂? 秋招的大公司非常多&#xff0c;也是非常好的&#xff0c;赶上了秋招&#xff0c;你基本工作就敲定了&#xff0c;在整个应届毕业生的人群中你就占据很大的优势了。 如何准备应届校招&#xff1f; 一、做好规划&#xff0c;把…...

Go语言入门心法(五): 函数

Go语言入门心法(一): 基础语法 Go语言入门心法(二): 结构体 Go语言入门心法(三): 接口 Go语言入门心法(四): 异常体系 Go语言入门心法(五): 函数 一: go语言函数认知 函数相关认知升维&#xff1a;函数的功能就是把相对独立的某个相同或者时类型的功能抽象处理,使之成为一个…...

gitignore文件的语法规则

行注释&#xff1a;以"#"符号开头的行表示注释&#xff0c;Git会忽略这些行。空行&#xff1a;空行会被忽略。文件和目录规则&#xff1a; 可以使用通配符来匹配文件和目录。常用的通配符有&#xff1a; “*”&#xff1a;匹配0个或多个字符。“?”&#xff1a;匹配…...

vscode提示扩展主机在过去5分钟内意外终止了3次,解决方法

参考链接&#xff1a; https://code.visualstudio.com/blogs/2021/02/16/extension-bisect https://code.visualstudio.com/docs/setup/uninstall#_clean-uninstall 使用vscode打开jupyter notebook记事本时&#xff0c;窗口右下角提示扩展主机在过去5分钟内意外终止了3次 而…...

【算法挨揍日记】day16——525. 连续数组、1314. 矩阵区域和

525. 连续数组 525. 连续数组 题目描述&#xff1a; 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组&#xff0c;并返回该子数组的长度。 解题思路&#xff1a; 本题的元素只有0和1&#xff0c;根据题目意思&#xff0c;我们可以把题目看成找一段最…...

k8s-13 存储之secret

Secret 对象类型用来保存敏感信息&#xff0c;例如密码、OAuth 令牌和 ssh key。 敏感信息放在 secret 中比放在 Pod 的定义或者容器镜像中来说更加安全和灵活 。 Pod 可以用两种方式使用 secret:作为 volume 中的文件被挂载到 pod 中的一个或者多个容器里 当 kubelet 为 pod 拉…...

什么是高阶成分(HOC)

高阶组件&#xff08;Higher-Order Component&#xff0c;HOC&#xff09;是一种在React中用于组件复用和逻辑抽象的设计模式。它本质上是一个函数&#xff0c;接受一个组件作为参数&#xff0c;并返回一个新的组件。 1. HOC的作用&#xff1a; HOC允许我们在不修改原始组件的…...

深度学习硬件配置推荐

目录 1. 基础推荐2. GPU显存与内存是一个1:4的配比?3. deep learning 入门和kaggle比赛4. 有些 Kaggle 比赛数据集很大,可能需要更多的 GPU 显存,请推荐显存4. GDDR6和HBM25. HDD 或 SATA SSD1. 基础推荐 假设您作为一个深度学习入门学者的需求,以下是一份推荐的电脑硬件配…...

数仓建设(一)

想了想&#xff0c;我们的数仓的建设是基于大数据平台进行的&#xff0c;中间也经历了比较曲折的过程。 每个行业都有自身的业务区别&#xff0c;不过很多还是比较相通的。 本文将全面讲解数仓建设规范&#xff0c;从数据模型规范&#xff0c;到数仓公共规范&#xff0c;数仓各…...

Springboot整合taos时序数据库TDengine

1.首先安装TDengine服务端在linux上 TDengine多种安装包的安装和卸载 - TDengine | 涛思数据安装过程直接去官网看,非常详细简单 2.出现的问题 windows连接 invalid app version 版本不对应 版本不对应的问题,需要在linux上安装的版本和windows client版本一致,不然w…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...