[LeetCode] LCR170. 交易逆序对的总数

题目描述：

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 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

题目链接：

. - 力扣（LeetCode）

题目主要思路：

其实就是归并分治的思想，以排升序为例，假如当cur1 > cur2 时，因为左右分区是排升序的，因此cur1以及cur1后面的部分一定是比cur2大的，因此{[cur1,mid], cur2}是一定构成逆序对的。

解题代码：

class Solution {int tmp[50000];
public:int reversePairs(vector<int>& record) {return mergeSort(record, 0, record.size()-1);}int mergeSort(vector<int>& record, int left, int right){// 递归结束条件if (left >= right) return 0;int mid = (left + right) >> 1;int ret = 0;ret += mergeSort(record, left, mid);ret += mergeSort(record, mid+1, right);int cur1 = left, cur2 = mid+1, i = 0;while (cur1 <= mid && cur2 <= right) {// 升序if (record[cur1] <= record[cur2]){tmp[i++] = record[cur1++];}else{ret += mid - cur1 + 1;tmp[i++] = record[cur2++];}}// 处理为排序的数据while (cur1 <= mid) {tmp[i++] = record[cur1++];}while (cur2 <= right) {tmp[i++] = record[cur2++];}// 将数据写入record中for (int i = left; i <= right; ++i){record[i] = tmp[i-left];}// 返回ret结果给上一层return ret;}
};