尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
归并排序三连:逆序对与翻转对精解
这篇文章来讲分治中的归并排序与前面的分治专题类似需要用到之前学过的排序的思想1.排序数组题目来源912. 排序数组 - 力扣LeetCode这道题是之前的题但是我们换成归并的思想来写归并同样需要用到递归的思想不同的是快排是一个一个进行排序归并则是一块一块进行排序并且归并还需要辅助数组来进行数据的更新因为思想之前排序专题已经讲过了所以这里就不多说了代码如下2.数组中的逆序对题目来源LCR 170. 交易逆序对的总数 - 力扣LeetCode以示例1来分析假如用枚举法将所有情况都枚举出来那时间复杂度为o(n^2)太慢了其实我们可以利用数组的有序性来进行优化在找逆序对的时候我们可以用归并排序来一遍边排一边统计因为左右都是有序的所以我们可以借助这个特性来统计逆序对不用一个一个地进行枚举具体代码如下其中tmp数组是用来暂时储存排好序的左右区间的3.计算右侧⼩于当前元素的个数题目来源315. 计算右侧小于当前元素的个数 - 力扣LeetCode这套题目同样可以用归并排序来进行优化利用归并排序的单调性可以快速地统计个数这道题和上一道题其实是一样的只是因为这道题要求返回的是一个数组因此我们需要多做一些处理代码如下因为我们需要记录某个位置的逆序对的个数但由于进行了归并排序原本的顺序会被打乱所以得用额外的数组来记录未进行排序前数组中元素各自的下标4.翻转对题目来源493. 翻转对 - 力扣LeetCode这道题目和第二道题基本上是一样的唯一的不同是比较的对象是nums[i]和2*num[j]因为这一个不同我们代码的书写也有所不同原本可以将排序和统计个数直接写在同一个循环里面但由于排序和统计的逻辑不同了所以要将这两个过程分开采用先统计再排序的方式又因为2*nums[j]可能超过了整形的最大值所以在这里我们需要做一下强制类型转换将其转换为long long类型代码如下以上就是本篇文章的全部内容了如果对你有帮助可以点个赞支持一下感谢各位的观看TA 关注的仓库 - 陌染青云 (mo-ran-qingyun) - Gitee.com这是我个人的gitee仓库,账号上文章的代码都会发到仓库里有兴趣可以看一下
RELATED

相关推荐

为Agent构建机器可读网站:技能注册与自描述接口实践

为Agent构建机器可读网站:技能注册与自描述接口实践

1. 为什么我要给 Agent 单独做一个网站先说结论:这个网站不是给人看的,是给 Agent 看的。更准确地说,是给那些需要调用外部能力、需要稳定获取结构化信息、需要一套可复用技能库的智能体系统看的。过去大半年,我一直在折腾各种 Ag…

📅 2026/10/14 9:25:41
知识工作插件化:构建采集、去重、拆卡、回顾的流水线

知识工作插件化:构建采集、去重、拆卡、回顾的流水线

很多长期记笔记的人,心里都压着一个不太好意思说出口的尴尬:自己沉淀的东西越来越多,真正能调用的却越来越少。我也经历过这个阶段,从浏览器剪藏、公众号收藏、文档草稿和随手记里攒下了一两千条零散内容,真到要用的时…

📅 2026/10/14 9:25:41
MCPCat:轻量级MCP客户端调试工具,让协议交互像cat一样透明

MCPCat:轻量级MCP客户端调试工具,让协议交互像cat一样透明

1. 从"MCPCat"这个名字说起:一个轻量级MCP客户端调试工具的设计初衷第一次看到"MCPCat"这个项目名,我的直觉是:这大概率是一个围绕MCP协议做文章的小工具,而且名字里带"Cat",多半跟&quo…

📅 2026/10/14 9:25:41
MORE NEWS

更多资讯

📰

AR人脸数据集稀疏表示实验:BMP读取、数据划分与SRC配置指南

简介:AR数据库是稀疏表示与鲁棒人脸识别研究中广泛使用的公开数据集;常见下载多为灰度图,此版本是经论文“PCA versus LDA”(IEEE TPAMI)预处理后的彩色裁剪版。压缩包共5201个文件,含2600张BMP彩色人脸图像…

📰

Scrum敏捷开发框架:角色分工与团队协作实践

1. Scrum框架概述 Scrum作为一种敏捷开发框架,最早由Jeff Sutherland和Ken Schwaber在1990年代提出。它通过固定周期的迭代(Sprint)来应对复杂项目的需求变化,相比传统瀑布式开发更适应现代快节奏的产品研发环境。我在多个互联网产…

📰

uni-app项目模板搭建指南:从目录结构到请求封装与多端调试

简介:这是一份面向具备一年以上uni-app开发经验的前端工程师的快速开发项目模板,由一位五年经验的Web前端开发者开源,旨在帮助开发者跳过重复搭建基础框架的过程,直接进入业务开发,同时也可作为进阶学习与参考的实战范…

📰

OpenCode高级用法:斜杠命令、Agent模式与上下文管理实战

用了那么久的OpenCode,我才发现自己一直把它用成了"高级聊天框"——问一句答一句,改个文件跑个测试,看起来挺顺,但真碰到跨十几个文件、反复改、还要回头查历史决策的任务,明显就使不上劲。问题多半不是模型…

📰

CS229机器学习课程资料包:讲义、作业与讲解的完整使用指南

简介:这份资料包面向希望系统学习机器学习的学习者与转行者,完整收录了吴恩达教授CS229课程的核心内容,涵盖讲义、作业与配套讲解,帮助读者在缺乏教师指导的情况下也能扎实掌握监督学习、无监督学习及强化学习等核心框架。资源共4…

📰

微网系统碳交易优化模型设计与Matlab实现

1. 项目背景与核心价值 微网系统作为分布式能源的重要载体,正在全球范围内加速普及。去年参与某工业园区微网项目时,我亲历了碳排放核算带来的成本压力——当月光伏出力不足导致柴油发电机运行时,仅碳税就增加了23%的运营成本。这种切身体验促…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬