【归并分而治之】逆序对的应对之策

1.前言

今天了解到一种比较有意思的题目解法，是专门针对逆序对的。下面来进行简单分享。

2.题目简介

题目链接：LINK

3.求解思路

我们一种解法是暴力求解，当然还有一种就是利用归并排序的思想。
下面我们着重来讲解归并排序这个求解思路。

首先，我们把统计整个序列分成两块，一左一右。我们首先单统计一下左边这块区域能够满足我们条件的逆序对数量，再统计一下右边这块区域能够满足我们条件的逆序对数量，之后再一左一右去统计剩下的逆序对数量，这样加起来就跟暴力求解一样了。

但是在这其中加上排序之后，结合归并排序的分治思想，可以更快。

为什么要这样做？

快在哪？

快就快在每次处理一左一右的逆序对个数的时候，因为我们是排好序的，所以可以快速统计。

为什么这种方法会想到结合归并排序？

因为这个思想非常贴近归并排序。

如何在一左一右中统计剩下的逆序对个数？

如果固定右边的数，那就得用升序
如果固定左边的数，那就得用降序

固定右边的数，用降序会怎么样？？？

如果固定右边的数，用降序，会出错，因为会统计到一些重复的逆序对。

固定左边的数，用升序也会有上面问题，是相同的道理的。

思路的本质是巧妙地结合了归并的思想

整体的话我感觉这个解题思路就是巧妙地结合了归并排序，然后就弄出了这么个方法。

4.示例代码

class Solution {
public:
//升序，向前找大int tmp[50001];int reversePairs(vector<int>& nums) {//利用归并分而治之的思路来解决问题return mergeSort(nums, 0, nums.size() - 1);}int mergeSort(vector<int>& nums, int left, int right){//只有一个数字或者不存在的区间直接返回0if(left >= right){return 0;}//左边的个数、右边可以匹配的个数，顺便进行排序int mid = (left + right) / 2;int ret = 0;ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);//一左一右的匹配对数int cur1 = left, cur2 = mid + 1, i = left;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];}return ret;}
};

---

---

EOF