力扣集训day05-北京尧图网络

思路主要是结合归并排序的思路进行解答大致就是1.先二分拆分merge拆到拆无可拆也就是左右边界重合为止至于lr这种情况是用来判断空链表这种特殊情况的。2.然后两两合并mergeTwoList这个其实是很简单的合并两个有序链表的写法两两比较小的放进去都不用新申请空间。3.最后逐层向上合并主函数归并的思路最难的就是这总地方了想想想上图假如有五个链表的情况最后的合并阶段实际肯定没这么......将就意思一下吧大概就这么个理代码ListNode* mergeTwoList(ListNode* list1, ListNode* list2) { ListNode* dummyhead new ListNode(); if (!list1 !list2)return list1 ? list1 : list2; ListNode* p1 list1, * p2 list2, * temp dummyhead; while (p1 p2) { if (p1-val p2-val) { temp-next p1; p1 p1-next; } else { temp-next p2; p2 p2-next; } temp temp-next; } temp-next (p1 ? p1 : p2); return dummyhead-next; } ListNode* merge(vectorListNode* lists, int l, int r) { if (l r)return lists[l]; if (l r)return nullptr; int mid (l r) / 2; return mergeTwoList(merge(lists, l, mid), merge(lists, mid 1, r)); } class Solution { public: ListNode* mergeKLists(vectorListNode* lists) { return merge(lists, 0, lists.size() - 1); } };小复习归并排序-核心思想先拆分后合并1分递归把数组从中间切为左右两半一直切到子区间只有 1 个元素2治合并将两个已经有序的子数组用双指针合并成一个有序数组3逐层向上合并最后整个数组有序-归并排序代码C版本)void merge(vectorint arr, int l, int mid, int r) { vectorint tmp; int i l, j mid1; while(i mid j r) { if(arr[i] arr[j]) tmp.push_back(arr[i]); else tmp.push_back(arr[j]); } while(i mid) tmp.push_back(arr[i]); while(j r) tmp.push_back(arr[j]); // 拷贝回原数组 for(int k 0; k tmp.size(); k) arr[l k] tmp[k]; } void mergeSort(vectorint arr, int l, int r) { if(l r) return; int mid l (r-l)/2; mergeSort(arr, l, mid); // 左半部分排序 mergeSort(arr, mid1, r); // 右半部分排序 merge(arr, l, mid, r); // 合并两个有序区间 }-复杂度1时间复杂度O(nlog n)是稳定排序2空间复杂度O(n)

力扣集训day05

相关推荐

MemOS MemReader 深度指南：把原始输入翻译成结构化记忆块的“记忆翻译官“

Docker部署XXL-JOB：从调度中心到执行器的完整实战指南

DAB双有源桥变换器：移相控制与软开关的工程实践指南

更多资讯

【JAVA毕设源码分享】基于spring boot的智慧医疗平台设计与实现(程序+文档+代码讲解+一条龙定制)

ARM学习笔记（8）

ESP8266与KiwisIoT实现低成本远程水位监测与告警系统

服装供应链SCM系统架构解析：库存周转的 MRP 运算与数据同源链路

Tinkercad电路仿真实战：从点亮LED到Arduino闪烁与555定时器

办公文档格式互转，多款文档转换工具能力客观记录

今日更新

Play Framework 迁移指南：移除 GlobalSettings，全面转向依赖注入（Scala 与 Java）

Numba 类型推断机制详解：从 Numba IR 到编译期类型重建的完整原理与实践

企业级项目dragonballz_e159-1的技术架构与实现方案

本周精选

深入解析Transformer多头注意力机制与工程优化

OpenClaw 的 Skills 跑学习任务，模型通道改到 TaoToken 通道行不行？

ChatGPT报错Oops, an error occurred! 全链路排查指南

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？