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

Python算法题集_排序链表

 Python算法题集_排序链表

  • 题148:排序链表
  • 1. 示例说明
  • 2. 题目解析
    • - 题意分解
    • - 优化思路
    • - 测量工具
  • 3. 代码展开
    • 1) 标准求解【冒泡大法】
    • 2) 改进版一【列表排序】
    • 3) 改进版二【数值归并排序】
    • 4) 改进版三【快慢指针归并排序】
  • 4. 最优算法

本文为Python算法题集之一的代码示例

题148:排序链表

1. 示例说明

  • 给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表

    示例 1:

    img

    输入:head = [4,2,1,3]
    输出:[1,2,3,4]
    

    示例 2:

    img

    输入:head = [-1,5,3,4,0]
    输出:[-1,0,3,4,5]
    

    示例 3:

    输入:head = []
    输出:[]
    

    提示:

    • 链表中节点的数目在范围 [0, 5 * 104]
    • -105 <= Node.val <= 105

    **进阶:**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?


2. 题目解析

- 题意分解

  1. 本题为对链表进行排序
  2. 基本的解法是双层循环冒泡法,所以基本的时间算法复杂度为O(n^2)

- 优化思路

  1. 通常优化:减少循环层次

  2. 通常优化:增加分支,减少计算集

  3. 通常优化:采用内置算法来提升计算速度

  4. 分析题目特点,分析最优解

    1. 链表的排序算法极为耗时

    2. 可以采用归并法对链表进行拆分然后合并

    3. 可以用列表排序法进行简单排序


- 测量工具

  • 本地化测试说明:LeetCode网站测试运行时数据波动很大,因此需要本地化测试解决这个问题
  • CheckFuncPerf(本地化函数用时和内存占用测试模块)已上传到CSDN,地址:Python算法题集_检测函数用时和内存占用的模块
  • 本题本地化超时测试用例自己生成,详见【最优算法章节】

3. 代码展开

1) 标准求解【冒泡大法】

链表双层,每次循环将一个最大值移到尾部,毫无意外的超时

无法通关,果然超时在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:@staticmethoddef sortList_base(head):if not head:return headif not head.next:return headbexchange = Truetmphead = ListNode(-1)tmphead.next = headtmpNode = tmpheadwhile bexchange and tmpNode:bexchange = FalsestartNode = tmpNodewhile startNode:if startNode.next:nextnode = startNode.nextif startNode.next.next:nextnode2 = nextnode.nextif nextnode.val > nextnode2.val:tmpNext = nextnode2.nextstartNode.next = nextnode2nextnode2.next = nextnodenextnode.next = tmpNextbexchange = TruestartNode = startNode.nextreturn tmphead.nextresult = cfp.getTimeMemoryStr(Solution.sortList_base, ahead)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 运行结果【链表长度1W】
函数 sortList_base 的运行时间为 20534.61 ms;内存使用量为 4.00 KB 执行结果 = 1

2) 改进版一【列表排序】

将链表存入列表结构,通过列表排序,最后再连接起来,性能优异,内存O(n)

性能卓越,超越96%在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:@staticmethoddef sortList_ext1(head):if not head:return headif not head.next:return headlist_node = []while head:list_node.append([head.val, head])head = head.nextsort_list = sorted(list_node, key=lambda x: x[0])for iIdx in range(len(sort_list)-1):sort_list[iIdx][1].next = sort_list[iIdx+1][1]sort_list[-1][1].next = Nonereturn sort_list[0][1]result = cfp.getTimeMemoryStr(Solution.sortList_ext1, ahead)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 运行结果【链表长度1W】
函数 sortList_ext1 的运行时间为 2.99 ms;内存使用量为 16.00 KB 执行结果 = 1

3) 改进版二【数值归并排序】

使用递归设计,用值定位将链表拆分排序;递归的最大层次为990,因此链表长度在2^990次方内都不会溢出

不值一提,超过06%在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:@staticmethoddef sortList_ext2(head):if not head:return headmin_val = max_val = head.valcurnode = headwhile curnode:min_val = min(min_val, curnode.val)max_val = max(max_val, curnode.val)curnode = curnode.nextif min_val == max_val:return headmid_val = (min_val + max_val) // 2head1 = ListNode(0) last1 = head1 head2 = ListNode(0) last2 = head2 curnode = headwhile curnode:if curnode.val <= mid_val:last1.next = curnodelast1 = last1.next else:last2.next = curnodelast2 = last2.nextcurnode = curnode.next last1.next = Nonelast2.next = None head1 = Solution.sortList_ext2(head1.next) head2 = Solution.sortList_ext2(head2.next)curnode = head1while curnode.next:curnode = curnode.nextcurnode.next = head2return head1result = cfp.getTimeMemoryStr(Solution.sortList_ext2, ahead)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 运行结果
函数 sortList_ext2 的运行时间为 71.03 ms;内存使用量为 0.00 KB 执行结果 = 1

4) 改进版三【快慢指针归并排序】

使用递归设计,用快慢指针将链表拆分排序;递归的最大层次为990,因此链表长度在2^990次方内都不会溢出

马马虎虎,超越72%在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:@staticmethoddef sortList_ext3(head):if not head or not head.next:return headslownode, fastnode = head, head.nextwhile fastnode and fastnode.next:fastnode, slownode = fastnode.next.next, slownode.nextmidnode, slownode.next = slownode.next, None leftlink, rightlink = Solution.sortList_ext3(head), Solution.sortList_ext3(midnode)tmpnode = headnode = ListNode(0)while leftlink and rightlink:if leftlink.val < rightlink.val:tmpnode.next, leftlink = leftlink, leftlink.nextelse:tmpnode.next, rightlink = rightlink, rightlink.nexttmpnode = tmpnode.nexttmpnode.next = leftlink if leftlink else rightlinkreturn headnode.nextresult = cfp.getTimeMemoryStr(Solution.sortList_ext3, ahead)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 运行结果
函数 sortList_ext3 的运行时间为 19.02 ms;内存使用量为 0.00 KB 执行结果 = 1

4. 最优算法

根据本地日志分析,最优算法为第2种sortList_ext1,如果内存要O(1)的话,则最优算法为第4种sortList_ext3

iLen = 10000
nums = [iLen - x for x in range(iLen)]
def generateOneLinkedList(data):head = ListNode()current_node = headfor num in data:new_node = ListNode(num)current_node.next = new_nodecurrent_node = new_nodereturn head.next
ahead = generateOneLinkedList(nums)
result = cfp.getTimeMemoryStr(Solution.sortList_base, ahead)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 算法本地速度实测比较
函数 sortList_base 的运行时间为 20534.61 ms;内存使用量为 4.00 KB 执行结果 = 1
函数 sortList_ext1 的运行时间为 2.99 ms;内存使用量为 16.00 KB 执行结果 = 1
函数 sortList_ext2 的运行时间为 71.03 ms;内存使用量为 0.00 KB 执行结果 = 1
函数 sortList_ext3 的运行时间为 19.02 ms;内存使用量为 0.00 KB 执行结果 = 1

一日练,一日功,一日不练十日空

may the odds be ever in your favor ~

相关文章:

Python算法题集_排序链表

Python算法题集_排序链表 题148&#xff1a;排序链表1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【冒泡大法】2) 改进版一【列表排序】3) 改进版二【数值归并排序】4) 改进版三【快慢指针归并排序】 4. 最优算法 本文为Python算法题集之一的…...

红日靶场2学习

靶场下载来自&#xff1a; http://vulnstack.qiyuanxuetang.net/vuln/detail/3/ 靶场统一登录密码&#xff1a;1qazWSX 按大佬的说法是 环境需要模拟内网和外网两个网段&#xff0c;PC端虚拟机相当于网关服务器&#xff0c;所以需要两张网卡&#xff0c;一个用来向外网提供web…...

将 下载下来的 jar 包 安装到本地的 maven 仓库中

使用管理员权限 打开一个 cmd 窗口输入 mvn -v 查看 maven 版本由于之前 并没有这样的操作所以第一次 执行的时候 提示 命令不存在所以需要将 maven 软件中的 bin 文件的目录 添加到 环境变量中 的 path 变量 中本机路径为:D:\Program Files (x86)\apache-maven-3.5.2\bin C:\…...

Qt初使用(使用Qt创建项目,在创建的项目中添加类,Qt中输出内容到控制台,设置窗口大小和窗口标题,Qt查看说明文档)

目录 一.创建带模板的项目新建项目运行在文件中查看该项目文件 二.在创建好的项目中添加类三.创建空项目&#xff08;不使用自带的模板&#xff09;四.Qt中输出内容到控制台五.设置窗口大小 , 窗口标题 ,固定窗口大小QWidget组件的说明 六.Pro文件帮助文档 按windows键&#xf…...

【黑马程序员】C++运算符重载

文章目录 运算符重载加号运算符重载成员函数实现运算符重载全局函数实现运算符重载全局函数实现函数重载 左移运算符重载递增运算符重载赋值运算符重载关系运算符重载函数调用运算符重载 运算符重载 对已有的运算符重新进行定义&#xff0c;赋予其另一种功能&#xff0c;以适应…...

Java中的乐观锁和悲观锁

使用场景及用法 悲观锁 总是假设最坏的情况&#xff0c;每次去拿数据的时候都认为别人会修改&#xff0c;所以每次在拿数据的时候都会上锁&#xff0c;这样别人想拿这个数据就会阻塞直到它拿到锁&#xff08;共享资源每次只给一个线程使用&#xff0c;其它线程阻塞&#xff0c;…...

从Unity到Three.js(计时器、Transform)

计时器、模型对象平移函数、枚举定义的使用 对应unity中的一些常用功能 import * as THREE from three;const scene new THREE.Scene(); const camera new THREE.PerspectiveCamera(60, window.innerWidth / window.innerHeight, 0.1, 1000);const renderer new THREE.WebG…...

红日靶场(初学)

按照以前的来说一般是有两层网络的内网和外网 这个也是这样的 所以需要两张网卡&#xff0c;一个用来向外网提供web服务&#xff0c;一个是通向内网 以下就是配置 以下就是一些相关信息 外网网段是写成了192.168.111.1/24 WEB PC DC kali 开始扫描 nmap -sS -sV -Pn -T4 19…...

【PyTorch】改变张量(Tensor)形状操作

PyTorch深度学习总结 第二章 PyTorch中改变张量(Tensor)形状操作 文章目录 PyTorch深度学习总结一、前言二、改变张量形状 一、前言 上文讲解了张量生成和信息获取的知识&#xff0c;本文将针对张量的操作进行详细讲解。 二、改变张量形状 1、改变张量形状的函数总结&#x…...

《金融人工智能:用python实现ai量化交易》

融合了数学、python、深度学习以及金融知识&#xff0c;是本推荐的好书。请收藏本文&#xff0c;读后再给大学总结。...

位运算+leetcode ( 2 )

题一&#xff1a;只出现一次的数字&#xff08;1&#xff09; 1.链接 136. 只出现一次的数字 - 力扣&#xff08;LeetCode&#xff09; 2.思想 借用位运算中异或操作符的特点&#xff0c;a^a0&#xff0c;0^aa先定义一个sum0就用一个循环来遍历这个数组&#xff0c;每次都进行…...

17 ABCD数码管显示与动态扫描原理

1. 驱动八位数码管循环点亮 1.1 数码管结构图 数码管有两种结构&#xff0c;共阴极和共阳极&#xff0c;ACX720板上的是共阳极数码管&#xff0c;低电平点亮。 1.2 三位数码管等效电路图 为了节约I/O接口&#xff0c;各个数码管的各段发光管被连在一起&#xff0c;通过sel端…...

【Zigbee课程设计系列文章】Zigbee开发环境搭建

【Zigbee课程设计系列文章】Zigbee开发环境搭建 前言IAR 下载安装Z-Stack协议栈安装 &#x1f38a;项目专栏&#xff1a;【Zigbee课程设计系列文章】&#xff08;附详细使用教程完整代码原理图完整课设报告&#xff09; 前言 &#x1f451;由于无线传感器网络&#xff08;也即…...

[Linux开发工具]项目自动化构建工具-make/Makefile

&#x1f4d9; 作者简介 &#xff1a;RO-BERRY &#x1f4d7; 学习方向&#xff1a;致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f4d2; 日后方向 : 偏向于CPP开发以及大数据方向&#xff0c;欢迎各位关注&#xff0c;谢谢各位的支持 目录 1.背景2.依赖关系和依…...

PLC_博图系列☞参数实例

PLC_博图系列☞参数实例 文章目录 PLC_博图系列☞参数实例背景介绍参数实例参数实例的工作原理创建参数实例将实例作为参数传送 关键字&#xff1a; PLC、 西门子、 博图、 Siemens 、 参数实例 背景介绍 这是一篇关于PLC编程的文章&#xff0c;特别是关于西门子的博图软件…...

LLaMA 2 和 QianWen-14B

阿里云通义千问14B模型开源&#xff01;性能超越Llama2等同等尺寸模型 - 科技新闻 - EDA365电子论坛网 LLaMA 2 的硬件要求&#xff1a; LLaMA 2 系列模型有不同的参数量版本&#xff0c;如7B、13B和70B等。对于不同大小的模型&#xff0c;其硬件需求也有所不同。以下是一些硬…...

浅谈Java常见设计模式及实例

前言 Java 中常用的设计模式有很多种&#xff0c;其实平常用到的还比较少&#xff0c;但是还是有必要了解一下&#xff0c;可以按照实际情况运用到我们的代码中。按照类型可以基本分解为&#xff0c;创建型模式、结构型模式和行为型模式。 创建型模式 (Creational Patterns) 1…...

【RISC-V DSP设计】基于CEVA DSP架构的指令集分析(一)-总体介绍

目录 一、引言 二、CEVA-BX1™ DSP Library 概述 三、CEVA-BX1™ DSP Library 功能与特点 四、CEVA-BX1™ DSP Library 优势 今天开始我们继续对CEVA DSP的架构和指令集进行分析&#xff0c;基于对CEVA DSP的分析和了解&#xff0c;后续可以进行基于RISC-V内核架构的DSP指令…...

Rust标量类型详解

在Rust中&#xff0c;数据类型分为标量类型和复合类型。本篇博客将重点介绍Rust的标量类型&#xff0c;其中包括整数类型、浮点类型、布尔类型以及字符类型。 整数类型 Rust提供了多种整数类型&#xff0c;分为带符号整数和无符号整数。带符号整数表示可以为正数、零或负数&a…...

【双指针】【C++算法】1537. 最大得分

作者推荐 【深度优先搜索】【树】【图论】2973. 树中每个节点放置的金币数目 本文涉及知识点 双指针 LeetCoce 1537. 最大得分 你有两个 有序 且数组内元素互不相同的数组 nums1 和 nums2 。 一条 合法路径 定义如下&#xff1a; 选择数组 nums1 或者 nums2 开始遍历&…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...