插头 东莞网站建设,文学网站怎样建设,网站优化的学习,灵犀科技 高端网站建设首页目录
力扣LCR 170. 交易逆序对的总数
解析代码1
解析代码2 力扣LCR 170. 交易逆序对的总数
LCR 170. 交易逆序对的总数
难度 困难
在股票交易中#xff0c;如果前一天的股价高于后一天的股价#xff0c;则可以认为存在一个「交易逆序对」。请设计一个程序#xff0c;输…目录
力扣LCR 170. 交易逆序对的总数
解析代码1
解析代码2 力扣LCR 170. 交易逆序对的总数
LCR 170. 交易逆序对的总数
难度 困难
在股票交易中如果前一天的股价高于后一天的股价则可以认为存在一个「交易逆序对」。请设计一个程序输入一段时间内的股票交易记录 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
class Solution {
public:int reversePairs(vectorint record) {}; 解析代码1 用归并排序求逆序数是很经典的方法主要就是在归并排序的合并过程中统计出逆序对的数量也就是在合并两个有序序列的过程中能够快速求出逆序对的数量。
如果将数组从中间划分成两个部分那么我们可以将逆序对产生方式划分成三组
逆序对中两个元素全部从左数组中选择。逆序对中两个元素全部从右数组中选择。逆序对中两个元素一个选左数组另一个选右数组。 根据排列组合的分类相加原理三种情况下产生的逆序对的总和正好等于总的逆序对数量。而这个思路正好匹配归并排序的过程
先排序左数组。再排序右数组。左数组和右数组合二为一。 因此我们可以利用归并排序的过程先求出左半数组中逆序对的数量再求出右半数组中逆序对的数量最后求出⼀个选择左边另⼀个选择右边情况下逆序对的数量三者相加即可。
class Solution {vectorint tmp;
public:int reversePairs(vectorint record) {tmp.resize(record.size());return mergeSortCnt(record, 0, record.size() - 1);}int mergeSortCnt(vectorint arr, int left, int right){ // 解法一找出该数之前有多少个数比我大 - 升序if(left right)return 0;int ret 0, mid (left right) 1;// 左边逆序对的个数排序 右边逆序对的个数排序ret mergeSortCnt(arr, left, mid);ret mergeSortCnt(arr, mid 1, right);// 一左一右逆序对的个数int cur1 left, cur2 mid 1, i 0;while(cur1 mid cur2 right){if(arr[cur1] arr[cur2]){ // 此时cur2后面的都是比cur1小的ret mid - cur1 1;tmp[i] arr[cur2];}else{tmp[i] arr[cur1];}}// 处理排序while (cur1 mid) tmp[i] arr[cur1];while (cur2 right) tmp[i] arr[cur2];for (int j left; j right; j)arr[j] tmp[j - left];return ret;}
}; 解析代码2
在代码一的基础上可以选择找出该数之前有多少个数比我小 - 降序
class Solution {vectorint tmp;
public:int reversePairs(vectorint record) {tmp.resize(record.size());return mergeSortCnt(record, 0, record.size() - 1);}int mergeSortCnt(vectorint arr, int left, int right){ // 解法二找出该数之前有多少个数比我小 - 降序if(left right)return 0;int ret 0, mid (left right) 1;// 左边逆序对的个数排序 右边逆序对的个数排序ret mergeSortCnt(arr, left, mid);ret mergeSortCnt(arr, mid 1, right);// 一左一右逆序对的个数int cur1 left, cur2 mid 1, i 0;while(cur1 mid cur2 right){if(arr[cur1] arr[cur2]){ // 此时cur2后面的都是比cur1小的// ret mid - cur1 1;// tmp[i] arr[cur2];ret right - cur2 1;tmp[i] arr[cur1]; // 降序}else{// tmp[i] arr[cur1];tmp[i] arr[cur2]; // 降序}}// 处理排序while (cur1 mid) tmp[i] arr[cur1];while (cur2 right) tmp[i] arr[cur2];for (int j left; j right; j)arr[j] tmp[j - left];return ret;}
};
