链接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;}};