初识算法 · 分治(3)
初识算法 · 分治(3)
前言：
本文的主题是分治，通过两道题目讲解，一道是归并排序，一道是求逆序对。 链接分别为：
LCR 170. 交易逆序对的总数 - 力扣（LeetCode） 题目分为三个部分讲解，一是题目解析，二是算法原理，三是算法编写，那么，话不多说，直接进行主题咯。
归并排序
题目解析
其实这个题目我们已经在分治1里面做过了，但是在分治1里面使用的是快排，本文介绍分治的另一种算法，即归并排序。
直接就进入原理吧！
算法原理
对于归并排序来说，基本思想是将数组不断的划分，不断的划分，直到划分到了一个数的情况，这么做的原因是为了后面方便合并数组，你想，如果存在两个有序数组，我们想要合并这个有序数组是不是十分容易？
一个双指针就可以搞定了。
那么对于归并算法同理，我们将数组不断的划分，不断的划分，直到划分为一个元素，此时，我们将该元素视为有序的，所以分治的第一步就完成了，我们应该递归回去了。回去之后，只需要完成一个操作就可以了，也就是合并有序数组。
那么对于归并排序来说，是将左右划分，并排好序，最后合并，这其实就是树的后序遍历：
对于快排来说，是先确定好了一个元素的位置，然后排序左右两边，这实际上是一种前序遍历：
现在直接算法编写吧！
算法编写
class Solution
{
public:
vector<int> tmp;
void MergeSort(vector<int>& nums, int left, int right)
{
if(left >= right) return;
//划分中间值
int mid = (right + left) >> 1;
MergeSort(nums, left, mid);
MergeSort(nums, mid + 1, right);
//开始合并数组
int cur1 = left, cur2 = mid + 1, i = 0;
while(cur1 <= mid && cur2 <= right)
tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
while(cur1 <= mid) tmp[i++] = nums[cur1++];
while(cur2 <= right) tmp[i++] = nums[cur2++];
//开始复原
for(int i = left; i <= right; i++)
nums[i] = tmp[i - left];
}
vector<int> sortArray(vector<int>& nums)
{
tmp.resize(nums.size());
MergeSort(nums, 0, nums.size() - 1);
return nums;
}
};求逆序对总数
题目解析
在大一或者是大二的时候，多多少少都是学习过逆序对的，逆序对的概念就是前面的数字大于后面的数组，那么这两个数组成的数对，就成为逆序对。
那么题目是给我们一个数组，让我们求该数组里面的逆序对的个数。
算法原理
对于该题目，我们可以直接脑袋一空，直接就思考如何进行暴力解法，那多简单，是吧！
我们直接两个for循环，第一个For循环用来固定一个数，遍历其他数，判断是否满足逆序对的条件即可。该暴力解法的时间复杂度是O(N^2)，在这道题目肯定是跑不过的，要不然也太对不起hard标签了。
所以，对于这道题目我们可以使用归并的思想，可能部分同学会觉得归并的思想和这道题并不搭边，我们不妨简单思考一下：
我们要求逆序对，那么该数组划分为两个区间之后，左边的逆序对 + 右边的逆序对，最后从左边选择数，再从右边选择数计算剩余的逆序对，三个逆序对的数一相加，我们就可以得到了总的逆序对个数。
但是但是，如果我们直接就是左边遍历右边遍历，那和第一种暴力解法也没有好到哪里去，所以从左边找和从右边找的时候，我们如果带上排序试试？
比如我们将左右两个数的逆序对找到了之后，顺便将这两个区间排序，那么，如果我们从左边找到一个数，从右边找一个数，如果左边的数字大于右边的数字，那么左区间的后面的数是不是都大于了后面的数字了？
这就爽了，我们直接就是+= mid - cur1 + 1就可以了。
那么排序我们排升序还是降序呢？
如果我们排序的是降序，遍历的过程，是极大有可能出现重复的：
此时这个策略就不可以了，现在的策略是找到有多少个数比他大。但是如果我们换一个策略呢？
找有多少个数比他小呢？
此时降序就十分吃香了。
所以降序和升序实际上都是可以的。
算法编写
int tmp[50010];
public:
int reversePairs(vector<int>& nums)
{
return mergeSort(nums, 0, nums.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);
ret += 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;
}感谢阅读！
腾讯云开发者
