分治算法(6)_归并排序_交易逆序对的总数
个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创分治算法(6)_归并排序_交易逆序对的总数
收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌
目录
温馨提示:
1. 题目链接:
2. 题目描述:
3. 解法:
算法思路:
方法一：快速统计出某个数前面有多少个数比它大(升序)
方法二：快速统计出某个数后面有多少个数比它小(降序)
代码展示:
结果分析:
温馨提示:
这里需要有归并排序的相关知识, 如果对归并排序还不是很了解的宝子们, 可以先去下方链接进行查看:
分治算法(5)_归并排序_排序数组-CSDN博客
1. 题目链接:
OJ链接 : 交易逆序对的总数
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. 逆序对中两个元素: 全部从右数组中选择
3. 逆序对中两个元素: 一个选左数组另一个选右数组
根据排列组合的分类相加原理, 三种情况下产生的逆序对的总和, 正好等于总的逆序对数量.
示例:
因此, 我们可以利用对并排序的过程, 先求出左半数组中逆序对的数量, 再求出右半数组中逆序对的数量, 最后求出一个选择左边, 另一个选择右边情况下逆序对的数量. 三者相加即可.
为什么要这么做?
在归并排序合并过程中, 我们得到的是两个有序的数组. 我们是可以利用数组的有序性, 快速统计出逆序对的数量, 而不是将所有情况都枚举出来.
最核心的问题, 如何在合并两个有序数组的过程中, 统计出逆序对的数量?
合并两个有序序列时求逆序对的方法有两种:
1. 快速统计出某个数前面有多少个数比它大
2. 快速统计出某个数后面有多少数比它小
方法一：快速统计出某个数前面有多少个数比它大(升序)
通过一个示例来演示方法一：
假定已经有两个已经有序的序列以及辅助数组 left = [5, 7, 9] right = [4, 5, 8] help = []，通过合并两
个有序数组的过程，来求得逆序对的数量：
规定如下定义来叙述过程 :
cur1 遍历 left 数组，cur2 遍历 right 数组
ret 记录逆序对的数量
第⼀轮循环：
left[cur1] > right[cur2]，由于两个数组都是升序的，那么我们可以断定，此刻 left 数组中
[cur1, 2] 区间内的 3 个元素均可与 right[cur2] 的元素构成逆序对，因此可以累加逆序对的数量 ret
+= 3，并且将 right[cur2] 加⼊到辅助数组中，cur2++ 遍历下⼀个元素。
第⼀轮循环结束后：left = [5, 7, 9] right = [x, 5, 8] help = [4] ret = 3 cur1 = 0 cur2 = 1
第⼆轮循环：
left[cur1] == right[cur2]，因为 right[cur2] 可能与 left 数组中往后的元素构成逆序对，因此我
们需要将 left[cur1] 加⼊到辅助数组中去，此时没有产生逆序对，不更新 ret。
第⼆轮循环结束后：left = [x, 7, 9] right = [x, 5, 8] help = [4, 5] ret = 3 cur1 = 1 cur2 = 1
第三轮循环：
left[cur1] > right[cur2]，与第⼀轮循环相同，此刻 left 数组中[cur1, 2] 区间内的 2 个元素均可
与 right[cur2] 的元素构成逆序对，更新 ret 的值为 ret += 2，并且将 right[cur2] 加⼊到辅助数组中
去，cur2++ 遍历下⼀个元素。
第三轮循环结束后：left = [x, 7, 9] right = [x, x, 8] help = [4, 5, 5] ret = 5 cur1 = 1 cur2 = 2
第四轮循环：
left[cur1] < right[cur2]，由于两个数组都是升序的，因此我们可以确定 left[cur1] 比 right 数
组中的所有元素都要小。left[cur1] 这个元素是不可能与 right 数组中的元素构成逆序对。因此，⼤胆的将 left[cur1] 这个元素加入到辅助数组中去，不更细 ret 的值。
第四轮循环结束后：left = [x, x, 9] right = [x, x, 8] help = [4, 5, 5, 7] ret = 5 cur1 = 2 cur2 = 2
第五轮循环：
left[cur1] > right[cur2]，与第⼀、第三轮循环相同。此时 left 数组内的 1 个元素能与
right[cur2] 构成逆序对，更新 ret 的值，并且将 right[cur2] 加⼊到辅助数组中去。
第五轮循环结束后：left = [x, x, 9] right = [x, x, x] help = [4, 5, 5, 7, 8] ret = 6 cur1 = 2 cur2 = 2
处理剩余元素：
• 如果是左边出现剩余，说明左边剩下的所有元素都是比右边元素⼤的，但是它们都是已经被计算过的（我们以右边的元素为基准的），因此不会产生逆序对，仅需归并排序即可。
• 如果是右边出现剩余，说明右边剩下的元素都是比左边大的，不符合逆序对的定义，因此也不需要处理，仅需归并排序即可
整个过程只需将两个数组遍历⼀遍即可，时间复杂度为 O(N)。
由上述过程我们可以得出方法⼀统计逆序对的关键点：
在合并有序数组的时候，遇到左数组当前元素 > 右数组当前元素时，我们可以通过计算左数组中剩余元素的长度，就可快速求出右数组当前元素前面有多少个数比它大，对比解法一中一个一个枚举逆序对效率快了许多。
方法二：快速统计出某个数后面有多少个数比它小(降序)
依旧通过一个示例来演示方法二：
假定已经有两个已经有序的序列以及辅助数组 left = [5, 7, 9] right = [4, 5, 8] help = []，通过合并两
个有序数组的过程，来求得逆序对的数量：
规定如下定义来叙述过程 :
cur1 遍历 left 数组，cur2 遍历 right 数组
ret 记录逆序对的数量
第⼀轮循环：
left[cur1] > right[cur2]，先不要着急统计，因为我们要找的是当前元素后⾯有多少比它小的，
这里虽然出现了一个，但是 right 数组中依旧还可能有其余比它小的。因此此时仅将 right[cur2] 加⼊
到辅助数组中去，并且将 cur2++。
第⼀轮循环结束后：left = [5, 7, 9] right = [x, 5, 8] help = [4] ret = 0 cur1 = 0 cur2 = 1
第⼆轮循环：
left[cur1] == right[cur2]，由于两个数组都是升序，这个时候对于元素 left[cur1] 来说，我们已
经可以断定 right 数组中[0, cur2) 左闭右开区间上的元素都是比它小的。因此此时可以统计逆序对的数量 ret += cur2 - 0，并且将 left[cur1] 放⼊到辅助数组中去，cur1++ 遍历下⼀个元素。
第二轮循环结束后：left = [x, 7, 9] right = [x, 5, 8] help = [4, 5] ret = 1 cur1 = 1 cur2 = 1
第三轮循环：
left[cur1] > right[cur2]，与第⼀轮循环相同，直接将 right[cur2] 加⼊到辅助数组中去，
cur2++ 遍历下⼀个元素。
第三轮循环结束后：left = [x, 7, 9] right = [x, x, 8] help = [4, 5, 5] ret = 1 cur1 = 1 cur2 = 2
第四轮循环：
left[cur1] < right[cur2]，由于两个数组都是升序的，这个时候对于元素 left[cur1] 来说，我们
依旧已经可以断定 right 数组中[0, cur2) 左闭右开区间上的元素都是比它小的。因此此时可以统计逆序对的数量 ret += cur2 - 0，并且将 left[cur1] 放⼊到辅助数组中去，cur1++ 遍历下⼀个元素。
第四轮循环结束后：left = [9] right = [8] help = [4, 5, 5, 7] ret = 3 cur1 = 2 cur2 = 2
第五轮循环：
left[cur1] > right[cur2]，与第⼀、第三轮循环相同。直接将 right[cur2] 加⼊到辅助数组中去，
cur2++ 遍历下⼀个元素。
第五轮循环结束后：left = [x, x, 9] right = [x, x, x] help = [4, 5, 5, 7, 8] ret = 3 cur1 = 2 cur2 = 2
处理剩余元素：
• 如果是左边出现剩余，说明左边剩下的所有元素都是比右边元素大的，但是相比较于方法一，逆序对的数量是没有统计过的。因此，我们需要统计 ret 的值：
◦ 设左边数组剩余元素的个数为 leave
◦ ret += leave * （cur2 - 0）
对于本题来说，处理剩余元素的时候， left 数组剩余 1 个元素，cur2 - 0 = 3，因此 ret 需要类加
上 3，结果为 6。与方法一求得的结果相同。
• 如果是右边出现剩余，说明右边剩下的元素都是⽐左边⼤的，不符合逆序对的定义，因此也不需要处理，仅需归并排序即可。
整个过程只需将两个数组遍历⼀遍即可，时间复杂度依旧为 O(N)。
由上述过程我们可以得出方法二统计逆序对的关键点：
在合并有序数组的时候，遇到左数组当前元素 <= 右数组当前元素时，我们可以通过计算右数组已经遍历过的元素的长度，快速求出左数组当前元素后面有多少个数比它大。
但是需要注意的是，在处理剩余元素的时候，方法二还需要统计逆序对的数量。
代码展示:
升序:
class Solution
{
int tmp[50010];
public:
int reversePairs(vector<int>& record) {
return mergesort(record, 0, record.size() - 1);
}
int mergesort(vector<int>& nums, int left, int right)
{
if(left >= right) return 0;
int ret = 0;
//找中间点, 将数组分成两部分
int mid = (left + right) >> 1;
//左边的个数 + 排序 + 右边的个数 + 排序
ret += mergesort(nums, left, mid) + mergesort(nums, mid + 1, right);
//一左一右的个数
int cur1 = left, cur2 = mid + 1, i = 0;
while(cur1 <= mid && cur2 <= right)
{
if(nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur1++];
else ret += mid - cur1 + 1, tmp[i++] = nums[cur2++];
}
//处理排序
while(cur1 <= mid) tmp[i++] = nums[cur1++];
while(cur2 <= right) tmp[i++] = nums[cur2++];
for(int j = left; j <= right; j++)
nums[j] = tmp[j - left];
return ret;
}
}; 
降序:
class Solution
{
int tmp[50010];
public:
int reversePairs(vector<int>& record) {
return mergesort(record, 0, record.size() - 1);
}
int mergesort(vector<int>& nums, int left, int right)
{
if(left >= right) return 0;
int ret = 0;
//找中间点, 将数组分成两部分
int mid = (left + right) >> 1;
//左边的个数 + 排序 + 右边的个数 + 排序
ret += mergesort(nums, left, mid) + mergesort(nums, mid + 1, right);
//一左一右的个数
int cur1 = left, cur2 = mid + 1, i = 0;
while(cur1 <= mid && cur2 <= right)
{
if(nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur2++];
else ret += right - cur2 + 1, tmp[i++] = nums[cur1++];
}
//处理排序
while(cur1 <= mid) tmp[i++] = nums[cur1++];
while(cur2 <= right) tmp[i++] = nums[cur2++];
for(int j = left; j <= right; j++)
nums[j] = tmp[j - left];
return ret;
}
};
结果分析:
