宁波网站建设服务公司电hua,ui作品集 网站怎么做,网络对企业管理的影响,网络架构拓扑图Python算法题集_排序链表 题148#xff1a;排序链表1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【冒泡大法】2) 改进版一【列表排序】3) 改进版二【数值归并排序】4) 改进版三【快慢指针归并排序】 4. 最优算法 本文为Python算法题集之一的… Python算法题集_排序链表 题148排序链表1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【冒泡大法】2) 改进版一【列表排序】3) 改进版二【数值归并排序】4) 改进版三【快慢指针归并排序】 4. 最优算法 本文为Python算法题集之一的代码示例
题148排序链表
1. 示例说明 给你链表的头结点 head 请将其按 升序 排列并返回 排序后的链表 。 示例 1 输入head [4,2,1,3]
输出[1,2,3,4]示例 2 输入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. 题目解析
- 题意分解
本题为对链表进行排序基本的解法是双层循环冒泡法所以基本的时间算法复杂度为O(n^2
- 优化思路 通常优化减少循环层次 通常优化增加分支减少计算集 通常优化采用内置算法来提升计算速度 分析题目特点分析最优解 链表的排序算法极为耗时 可以采用归并法对链表进行拆分然后合并 可以用列表排序法进行简单排序 - 测量工具
本地化测试说明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 执行结果 12) 改进版一【列表排序】
将链表存入列表结构通过列表排序最后再连接起来性能优异内存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, keylambda x: x[0])for iIdx in range(len(sort_list)-1):sort_list[iIdx][1].next sort_list[iIdx1][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 执行结果 13) 改进版二【数值归并排序】
使用递归设计用值定位将链表拆分排序递归的最大层次为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 执行结果 14) 改进版三【快慢指针归并排序】
使用递归设计用快慢指针将链表拆分排序递归的最大层次为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 执行结果 14. 最优算法
根据本地日志分析最优算法为第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 ~
