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

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

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 (归并排序链表)

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

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

相关文章

vscode使用

vscode 快捷键1、ctrl f 文件内搜索2、ctrlp 快速打开最近打开的文件3、ctrlshiltn 打开新的编辑器窗口4、ctrlshiftw 关闭编辑器5、ctrlhome 跳转到页头6、ctrlend 跳转到页尾 插件1、Markdown Preview 参考文章 https://zhuanlan.zhihu.com/p/113222681?utm_sourcecom.tenc…

React添加文件路径时使用@符号代替src目录(非creae-react-app)

在其它项目中看到的可以用符号来代替src目录&#xff0c;那么在自己的react项目中也必须得尝试一下。本人的项目不是通过create-react-app脚手架来创建的&#xff0c;无法使用craco或者的方案来实现。 jsconfig.json配置 用的vscode进行开发&#xff0c;查看项目当中是否存在js…

QT中使用QVTKOpenGLNativeWidget的简单教程以及案例,利用PCLVisualizer显示点云

先添加一个带有ui的QT应用程序。 一、在ui界面中添加QVTKOpenGLNativeWidget控件 先拖出来一个QOpenGLWidget控件 修改布局如下&#xff1a; 然后将QOpenGLWidget控件提升为QVTKOpenGLNativeWidget控件&#xff0c;步骤如下&#xff1a; 右击QOpenGLWidget窗口&#xff0c;选…

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

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

DirectX3D 正交投影学习记录

所谓正交投影变换&#xff0c;就是已知盒状可视空间内任意点坐标(x,y,z)&#xff0c;求解垂直投影到xy平面的对应点坐标。 按照这个定义&#xff0c;xyz坐标系本身就是正交坐标系&#xff0c;盒状可视空间内任意点的坐标(x,y,z)投影到(x,y)平面&#xff0c;只要简单地丢弃z坐标…

如何使用前端框架(React、Angular、Vue.js等)?该如何选择?

聚沙成塔每天进步一点点 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 欢迎来到前端入门之旅&#xff01;感兴趣的可以订阅本专栏哦&#xff01;这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域的朋友们量身打造的。无论你是完全的新手还是有一些基础的开发…

SLAM从入门到精通(dwa算法)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 要说搜路算法&#xff0c;这个大家都比较好理解。毕竟从一个地点走到另外一个地点&#xff0c;这个都是直觉上可以感受到的事情。但是这条道路上机…

基于SSM的视频播放系统的设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;Vue 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#xff1a;是 目录…

NSS [GWCTF 2019]枯燥的抽奖

NSS [GWCTF 2019]枯燥的抽奖 开题让我猜字符串&#xff0c;这种题目肯定不是猜&#xff0c;应该是类似于php伪随机数。 dirsearch扫他一下。 访问/check.php得到源码。 分析一下代码。 通过PHP伪随机数从字符库$str_long1中选取20个字符组成字符串&#xff0c;返回给我们前十…

UE5 运行时生成距离场数据

1.背景 最近有在运行时加载模型的需求&#xff0c;使用DatasmithRuntimeActor可以实现&#xff0c;但是跟在编辑器里加载的模型对比起来&#xff0c;室内没有Lumen的光照效果。 图1 编辑器下加载模型的效果 图2 运行时下加载模型的效果 然后查看了距离场的数据&#xff0c;发现…

【扩散模型从原理到实战】Chapter2 Hugging Face简介

文章目录 Hugging Face的核心功能介绍Hugging Face开源库Hugging Face开源库Gradio工具介绍参考资料 Hugging Face是机器学习从业者协作和交流的平台&#xff0c;成立于2016年&#xff0c;在纽约和巴黎设有办事处&#xff0c;团队成员来自世界各地&#xff0c;远程办公。 致力于…

封装一个Element-ui生成一个可行内编辑的表格(vue2项目)

这个封装的是一个供整个项目使用的表格,可多次复用.放在一个全局使用的公共组件文件下. 大致功能介绍,封装自定义指令,点击获得焦点,显示输入框,失去焦点显示文本内容,类型是字典决定类型,图片可以显示图片名还是上传图片 子组件 <script> export default {props: {//生…

SpringCloud ---day1

认识微服务 单体架构 微服务架构 方便进行打包上线,版本的更新上线,降低项目之间的耦合度,减少代码量巨大导致的编译/打包时间长的问题 SpringCloud简介 项目熟悉 业务流程 项目模块划分 服务拆分原则 什么时候拆: 对于一个初创的项目&#xff0c;首先要做的是验证项目的可…

el-table :span-method合并单元格

<el-table :data"tableData" :span-method"objectSpanMethod" border style"width: 100%" :height"300"><el-table-column type"index" label"序号" width"50"></el-table-column>&l…

ajax同步与异步,json-serve的安装与使用,node.js的下载

20.ajax json 轻量级的数据格式做配置文件网络传输 xml 重量级的数据格式 可扩展标记语言做配置文件网络传输 现在目前主流就是大量采用json做网络传输数据格式 1.ajax的概念: 与服务器进行’通信’的一种技术,能够实现异步的刷新页面 **同步:**按照顺序一步步的执行,容易造…

算法通过村第十四关-堆|黄金笔记|中位数

文章目录 前言数据流中的中位数的问题总结 前言 提示&#xff1a;我独自度过了太多的时光&#xff0c;沉默已成一种习惯。 帕瑞尔马卡姆《夜航西飞》 这个是一个比较难的题目&#xff0c;要不尝试一下看看。 数据流中的中位数的问题 参考题目地址&#xff1a;295. 数据流的中位…

MyBatisPlus-02

一 查询条件的三种 1.按条件查询 //方式一&#xff1a;按条件查询QueryWrapper qw new QueryWrapper();qw.lt("age",18);List<User> userList userDao.selectList(qw);System.out.println(userList); 2.lambda格式按条件查询 //方式二&#xff1a;lambda格…

基于EtherCAT的机器人多轴同步运动控制

随着工业自动化的发展&#xff0c;机器人在生产线上的应用越来越广泛。为了实现高效、精确的运动控制&#xff0c;机器人的多轴运动必须能够实现同步操作&#xff0c;它能够提高机器人的运动精度和稳定性&#xff0c;实现更高效的生产线操作。同时&#xff0c;它也为机器人的协…

WebGPU入门一

1 WebGPU学习开发环境配置 WebGPU的环境配置比较简单&#xff0c;不需要vite或webpack配置一个复杂的开发环境&#xff0c;直接使用.html文件即可。 1.1 支持WebGPU的浏览器 Chrome 113 beta测试版开始默认支持WebGPU。 1.2 index.html文件 创建index.html文件&#xff0c…

C++进阶篇1---继承

一、继承的概念和定义 1.1概念 继承机制是面向对象程序设计使代码可以复用的最重要的手段&#xff0c;它允许程序员在保持原有类特性的基础上进行扩展&#xff0c;增加功能&#xff0c;这样产生新的类&#xff0c;称为派生类。继承呈现了面向对象程序设计的层次结构&#xff…