本文主要是介绍每日OJ题_分治归并②_LCR 170. 交易逆序对的总数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
力扣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(vector<int>& record) {};
解析代码1
用归并排序求逆序数是很经典的方法,主要就是在归并排序的合并过程中统计出逆序对的数量,也就是在合并两个有序序列的过程中,能够快速求出逆序对的数量。
如果将数组从中间划分成两个部分,那么我们可以将逆序对产生方式划分成三组:
- 逆序对中两个元素:全部从左数组中选择。
- 逆序对中两个元素:全部从右数组中选择。
- 逆序对中两个元素:一个选左数组另一个选右数组。
根据排列组合的分类相加原理,三种情况下产生的逆序对的总和,正好等于总的逆序对数量。而这个思路正好匹配归并排序的过程:
- 先排序左数组。
- 再排序右数组。
- 左数组和右数组合二为一。
因此,我们可以利用归并排序的过程,先求出左半数组中逆序对的数量,再求出右半数组中逆序对的数量,最后求出⼀个选择左边,另⼀个选择右边情况下逆序对的数量,三者相加即可。
class Solution {vector<int> tmp;
public:int reversePairs(vector<int>& record) {tmp.resize(record.size());return mergeSortCnt(record, 0, record.size() - 1);}int mergeSortCnt(vector<int>& 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 {vector<int> tmp;
public:int reversePairs(vector<int>& record) {tmp.resize(record.size());return mergeSortCnt(record, 0, record.size() - 1);}int mergeSortCnt(vector<int>& 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;}
};
这篇关于每日OJ题_分治归并②_LCR 170. 交易逆序对的总数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!