每日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;
    }
};