【算法】分治：归并排序之LCR 170.交易逆序对的总数（hard）

系列专栏

双指针

模拟算法

分治思想

---

目录

1、题目链接

2、题目介绍

3、解法

4、代码

---

1、题目链接

LCR 159. 库存管理 III - 力扣（LeetCode）

2、题目介绍

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

3、解法

1. 逆序对的计算：
   在归并排序的合并步骤中，当我们将两个已排序的子数组合并成一个有序数组时，如果左侧子数组中的某个元素大于右侧子数组中的某个元素，那么左侧子数组中该元素之后的所有元素（包括该元素本身）都将与右侧子数组中的该元素形成逆序对。因此，我们可以通过计算这样的元素对数来统计逆序对的总数。

2. 具体实现：

   • 分割：将数组分成左右两部分，递归地对它们进行排序。
   • 合并与计数：在合并过程中，使用两个指针分别指向左右子数组的起始位置，比较两个指针所指向的元素。如果左侧元素大于右侧元素，则左侧元素及其之后的所有元素都将与右侧当前元素形成逆序对，因此逆序对数增加 mid - cur1 + 1（mid 是左右子数组的分界点，cur1 是左侧子数组的当前指针位置）。然后，将较小的元素放入临时数组 tmp 中，并移动相应的指针。
   • 复原：将临时数组 tmp 中的元素复制回原数组 record，以完成排序和逆序对的计算。
   • 时间复杂度：归并排序的时间复杂度为 O(n log n)，其中 n 是数组的长度。在合并过程中，我们遍历了每个元素一次，因此计算逆序对的额外时间复杂度也是 O(n log n)。
   • 空间复杂度：归并排序需要额外的空间来存储临时数组 tmp，其大小为 n，因此空间复杂度为 O(n)。

4、代码

//归并排序
//升序
class Solution {vector<int> tmp;
public:int reversePairs(vector<int>& record) {tmp.resize(record.size());return mergeSort(record, 0, record.size() - 1);}// 查找区间内的逆序对总数（归并排序思想）int mergeSort(vector<int>& record, int left, int right){if (left >= right) return 0;// 1. 找中点将数组分成两部分// [left,mid] [mid+1,right]int mid = (right - left) / 2 + left;int ret = 0;// 2. 左边的个数 + 排序 ,右边的个数 + 排序ret += mergeSort(record, left, mid);ret += mergeSort(record, mid + 1, right);// 3. 一左一右的个数（升序版本）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++];}}// 4. 处理排序过程while (cur1 <= mid) tmp[i++] = record[cur1++];while (cur2 <= right) tmp[i++] = record[cur2++];// 复原for (int i = left; i <= right; i++)record[i] = tmp[i - left];return ret;}
};

---

💗感谢阅读！💗

---