每日算法题2-北京尧图网络

链接LCR 170. 交易逆序对的总数 - 力扣LeetCode在股票交易中如果前一天的股价高于后一天的股价则可以认为存在一个「交易逆序对」。请设计一个程序输入一段时间内的股票交易记录record返回其中存在的「交易逆序对」总数。示例 1输入record [9, 7, 5, 4, 6]输出8解释交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。提示0 record.length 50000思路首先明确一点当把数组分为两部分时左边逆序对右边逆序对一左一右逆序对的数量和等于不分组的数量即我们可以把数组分为两部分算其逆序对因为这种将大化为两个小的部分和归并排序相似我们联想一下算一左一右时为升序左边如果大于右边则左当前位置之后都大于右边这个数。下面由代码和注释详细讲解注意由于习惯我把数组名改为了numsclass Solution {public://搞一个临时数组给归并排序使用int tem[50001];//优化方案这个数组大小可以看下面的sz来搞不需要一开始搞这么多int reversePairs(vectorint nums) {//将其分为两部分整体逆序对等于//左边一块逆序对右边一块逆序对一左一右找到的逆序对int sznums.size();return hanshu(nums,0,sz-1);}int hanshu(vectorint nums,int left,int right){//使用归并排序因为归并排序也是分两部分而且重要的是当左边和右边有序比较他们可以省事.if(leftright) return 0;int ret0;int mid(leftright)1;int lleft;int rmid1;rethanshu(nums,left,mid);rethanshu(nums,mid1,right);//开始排序我这次使用升序降序也可以不过思路小小变一下//注意这里是归并排序的时候同时开始计算retint i0;while(lmidrright){if(nums[l]nums[r]){//因为是找逆序对所以这个里只需变化temret不变tem[i]nums[l];//l是因为它小了r后面它也一定大不过没有逆序对了}else{tem[i]nums[r];retmid-l1;r;}}//将剩余数字加入tem中while(lmid){tem[i]nums[l];}while(rright){tem[i]nums[r];}//把tem的值给回numsfor(int oleft;oright;o){nums[o]tem[o-left];//因为tem从0开始所以o要减left;}return ret;}};

每日算法题2

相关推荐

如何用电脑键盘操控手机终端：OpenClaw on Android搭配Termux的SSH远程配置完全指南

JSP上机实习报告全攻略：从环境搭建到JDBC增删改查实战

@Value 只认容器，new 出来的对象拿不到值

更多资讯

变电站红外图像中的PT/CT检测：889张标注数据与YOLOv8实战

Oracle截取JSON字符串内容：JSON_VALUE与字符串函数实战

ZZU编译原理实验：NFA转DFA并最小化C++实现与避坑指南

雷神Thunderobot官方授权维修点指南：2026年10月高刷屏与风扇专项送修

钉钉考勤与审批规则落地：从签到双签逻辑到后台配置避坑指南

AI及学术网址导航：用JSON配置驱动静态导航页的完整实践

今日更新

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

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