企业官网建设流程全解析

链接：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

思路：

首先明确一点，当把数组分为两部分时，左边逆序对+右边逆序对+一左一右逆序对的数量和等于不分组的数量，即我们可以把数组分为两部分算其逆序对

因为这种将大化为两个小的部分和归并排序相似，我们联想一下，算一左一右时（为升序），左边如果大于右边则，左当前位置之后都大于右边这个数。

下面由代码和注释详细讲解：注意由于习惯我把数组名改为了nums

class Solution {

public:

//搞一个临时数组给归并排序使用

int tem[50001];

//优化方案，这个数组大小可以看下面的sz来搞不需要一开始搞这么多

int reversePairs(vector<int>& nums) {

//将其分为两部分整体逆序对等于

//左边一块逆序对+右边一块逆序对+一左一右找到的逆序对

int sz=nums.size();

return hanshu(nums,0,sz-1);

}

int hanshu(vector<int>& nums,int left,int right)

{

//使用归并排序，因为归并排序也是分两部分，而且重要的是当左边和右边有序，比较他们可以省事.

if(left>=right) return 0;

int ret=0;

int mid=(left+right)>>1;

int l=left;

int r=mid+1;

ret+=hanshu(nums,left,mid);

ret+=hanshu(nums,mid+1,right);

//开始排序我这次使用升序，降序也可以不过思路小小变一下

//注意这里是归并排序的时候同时开始计算ret

int i=0;

while(l<=mid&&r<=right)

{

if(nums[l]<=nums[r])

{

//因为是找逆序对，所以这个里只需变化tem，ret不变

tem[i++]=nums[l++];

//l++是因为它小了r后面它也一定大不过，没有逆序对了

}

else

{

tem[i++]=nums[r];

ret+=mid-l+1;

r++;

}

}

//将剩余数字加入tem中

while(l<=mid)

{

tem[i++]=nums[l++];

}

while(r<=right)

{

tem[i++]=nums[r++];

}

//把tem的值给回nums

for(int o=left;o<=right;o++)

{

nums[o]=tem[o-left];

//因为tem从0开始所以o要减left;

}

return ret;

}

};