归并排序算啊模板and三道困难级别的归并力扣算法题--LCR170，493，315

目录

归并排序算法模板：

1.1题目链接：LCR.170.交易逆序对的总数

1.2题目描述：

1.3解法(利用归并排序的过程--分治)：

2.1题目链接：315.计算右侧小于当前元素的个数

2.2题目描述：

2.3解法：

3.1题目链接：493.翻转对

3.2题目描述：

3.3解法：

---

归并排序算法模板：

class Solution {
public:vector<int> ret;vector<int> sortArray(vector<int>& nums) {ret.resize(nums.size());mergesort(nums,0,nums.size()-1);return ret;}void mergesort(vector<int>& nums, int left, int right){if(left>=right)return;//1.选择中间点划分区域int mid = (left + right)>>1;//[left,mid][mid+1,right]//2.把左右区间排序mergesort(nums,left,mid);mergesort(nums,mid+1,right);//3.合并两个有序数组int cur1 = left,cur2 = mid+1,i = 0;while(cur1<=mid&&cur2<=right)ret[i++] = nums[cur1] <= nums[cur2]?nums[cur1++]:nums[cur2++];//处理没有遍历完的数组while(cur1<=mid)ret[i++] = nums[cur1++];while(cur2<=right)ret[i++] = nums[cur2++];//4.还原for(int i = left;i<=right;i++)nums[i] = ret[i-left];}
};

1.1题目链接：LCR.170.交易逆序对的总数

1.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

1.3解法(利用归并排序的过程--分治)：

算法思路：

用归并排序求逆序数是很经典的问题，主要就是在归并排序的合并过程中统计出逆序对的数量，也就是在合并两个有序序列的过程中，能够快速求出逆序对的数量。

我们将这个问题分解成几个小问题，逐一破解这道题。

注意：默认都是升序，如果掌握升序的话，降序的归并过程也是可以解决解决问题的。

• 先解决第一个问题：为什么可以用归并排序？

如果我们将数组从中间划分成两个部分，那么我们可以将逆序对产生的方式划分成三组：

• 逆序对中两个元素：全部从左数组中选择
• 逆序对中两个元素：全部从右数组中选择
• 逆序对中两个元素：一个选左数组另一个选右数组

根据排列组合的分类相加原理，三种情况下产生的逆序对的总和，正好等于总的逆序对数量。

而这个思路正好匹配归并排序的过程：

• 先排序左数组；
• 再排序右数组
• 左数组和有数组合二为一。

因此，我们可以利用归并排序的过程，先求出左半数组中逆序对的数量，再求出右半数组逆序对的数量，最后求出一个选择左边，另一个选择右边情况下逆序对的数量，三者相加即可。

• 解决第二个问题，为什么要这么做？

在归并排序合并的过程中，我们得到的是两个有序的数组。我们是可以利用数组的有序性，快速统计出逆序对的数量，而不是将所有情况都枚举出来。

• 最核心的问题，如何在合并两个有序数组的过程中，统计出逆序对的数量？

合并两个有序序列时求逆序对的方法有两种：

1. 快速统计出某个数前面有多少个数比它大；
2. 快速统计出某个数后面有多少个数比它小；

快速统计出某个数前面有多少个数比它大

通过一个实例来演示方法一：
假定已经有两个已经有序的序列以及辅助数组left = [5,7,9] right = [4,5,8] help=[]，通过合并两个有序数组的过程，来求得逆序对的数量：

规定如下定义来叙述过程：

        cur1遍历left数组，cue2遍历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]区间内的两个元素均可与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)

由上述过程我们可以得出方法一统计逆序对的关键点：

在合并有序数组的时候，遇到左数组当前元素>右数组当前元素时，我们可以通过计算左数组中剩余元素的长度，就可快速求出右数组当前元素前面有多少个数比它大，对比解法一中一个一个枚举逆序对效率快了许多。

升序：

class Solution
{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;//1.找中间点，将数组分成两部分int mid = (left + right) >> 1;//[left, mid][mid+1 right]//2.左边的个数+排序+右边的个数+排序ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);//3.一左一右的个数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++];}}//4.处理一个排序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>& 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;//1.找中间点，将数组分成两部分int mid = (left + right) >> 1;//[left, mid][mid+1 right]//2.左边的个数+排序+右边的个数+排序ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);//3.一左一右的个数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++];}}//4.处理一个排序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;}
};

2.1题目链接：315.计算右侧小于当前元素的个数

2.2题目描述：

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

示例 1：

输入：nums = [5,2,6,1]
输出：[2,1,1,0] 
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

示例 2：

输入：nums = [-1]
输出：[0]

示例 3：

输入：nums = [-1,-1]
输出：[0,0]

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

2.3解法：

算法思路：

这一道题的解法与上一道题的解法是类似的，但是这一道题要求的不是求总的个数，而是要返回一个数组，记录每一个元素的右边有多少个元素比自己小。

但是在我们归并排序的过程中，元素的下标是会跟着变化的，因此我们需要一个辅助数组，来将数组元素和对应的下标捆绑在一起归并，也就是再归并元素的时候，顺势将下标也转移到对应的位置上。

算法流程：

• 创建两个全局的数组：

        vector<int>index:记录下标

        vector<int>ret:记录结果

index用来与原数组中对应位置的元素绑定，ret用来记录每个位置统计出来的逆序对的个数。

• countSmaller()主函数：

1. 计算nums数组的大小为n；
2. 初始化定义的两个全局的数组；(为两个数组开辟大小为n的空间；index初始化为数组小标；ret初始化为0)
3. 调用mergeSort()函数，并且返回ret结果数组。

• void mergeSort(vector<int>& nums, int left, int right)函数：

函数设计：通过修改全局的数组ret，统计出每一个位置对应的逆序对的数量，并且排序；无需返回值，因为直接对全局变量修改，当函数结束的时候，全局变量已经被修改成最后的结果。

• mergeSort()函数流程：

1. 定义递归出口：left>=right时，直接返回；
2. 划分区间：根据中点mid，将区间划分为[left,mid]和[mid+1,right];
3. 统计左右两个区间逆序对的数量：统计左边区间[left,mid]中每个元素对应的逆序对的数量到ret数组中，并排序；统计右边区间[mid+1,right]中每个元素对应的逆序对的数量到ret数组中，并排序。
4. 合并左右两个有序区间，并且统计出逆序对的数量：                                                     创建两个大小为right-left+1大小的辅助数组：tmpnums：排序用的辅助数组；                                                                                      tmpindex：处理下标用的辅助数组           

        初始化遍历数组的指针：cur1 = left(遍历左半部分数组) cur2 = mid+1(遍历右半边数组) dest = 0（遍历辅助数组）curRet（记录合并时产生的逆序对的数量）；                       

        循环合并区间：

• 当nums[cur1] <= nums[cur2]时：
  无需统计，直接归并，注意index也要跟住归并。
• 当nums[cur1] > nums[cur2]时：

        说明此时[cur2,right]之间的元素都是小于nums[cur1]的，需要累加到ret数组的index[cur1]位置上(因为index存储的是元素对应位置在原数组中1的下标)

        归并排序：不仅要将数据放在对应的位置上，也要将数据对应的坐标也放在对应的位置上，使数据与原始的下标绑定在一起移动

        处理归并排序中剩余的元素；

        将辅助数组的内容替换到原数组中去；

class Solution {
public:vector<int> index;  //记录nums中当前元素的原始下标vector<int> ret;int tmpNums[500010];int tmpIndex[500010];vector<int> countSmaller(vector<int>& nums) {int n = nums.size();ret.resize(n);index.resize(n);//初始化一下indexfor(int i = 0;i<n;i++)index[i] = i;MergeSort(nums, 0, n-1);return ret;}void MergeSort(vector<int>& nums, int left, int right){if(left>=right)return;//1.根据中间元素，划分区间int mid = (left + right)>>1;//[left,mid][mid+1,right]//2.先处理左右两部分MergeSort(nums, left, mid);MergeSort(nums, mid+1, right);//3.处理一左一右的情况int cur1 = left, cur2 = mid + 1,i = 0;while(cur1<=mid && cur2<=right){if(nums[cur1] <= nums[cur2]){tmpNums[i] = nums[cur2];tmpIndex[i++] = index[cur2++];}else{ret[index[cur1]] += right - cur2 + 1;tmpNums[i] = nums[cur1];tmpIndex[i++] = index[cur1++];}}//处理剩下的排序过程while(cur1 <= mid){tmpNums[i] = nums[cur1];tmpIndex[i++] = index[cur1++];}while(cur2 <= right){tmpNums[i] = nums[cur2];tmpIndex[i++] = index[cur2++];}//还原for(int i = left;i<=right;i++){nums[i] = tmpNums[i-left];index[i] = tmpIndex[i-left];}}
};

3.1题目链接：493.翻转对

3.2题目描述：

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

示例 1:

输入: [1,3,2,3,1]
输出: 2

示例 2:

输入: [2,4,3,5,1]
输出: 3

注意:

1. 给定数组的长度不会超过50000。
2. 输入数组中的所有数字都在32位整数的表示范围内。

3.3解法：

算法思路：
大思路与求逆序对的思路一样，就是利用归并排序的思想，将求整个数组的翻转对的数量，转换成三部分：左半区间翻转对的数量，右半区间翻转对的数量，一左一右选择时翻转对的数量。重点就是在合并区间过程中，如何计算出翻转对的数量。
与上个问题不同的是，上一道题我们可以一边合并一遍计算，但是这道题要求的是左边元素大于右边元素的两倍，如果我们直接合并的话，是无法快速计算出翻转对的数量的。
例如 left =［4,5, 6］ right =［3, 4,5］时，如果是归并排序的话，我们需要计算 left 数组中有多少个能与3组成翻转对。但是我们要遍历到最后一个元素6才能确定，时间复杂度较高。
因此我们需要在归并排序之前完成翻转对的统计。
下面依旧以一个示例来模仿两个有序序列如何快速求出翻转对的过程：
假定已经有两个已经有序的序列left =［4, 5, 6］ right =［1,2,3］。
用两个指针cur1 cur2遍历两个数组。

。对于任意给定的left[cur1]而言，我们不断地向右移动cur2，直到left［cur1］<=2*right［cur2］。此时对于 right 数组而言，cur2 之前的元素全部都可以与left［cur1］构成翻转
对
。随后，我们再将cur1 向右移动一个单位，此时 cur2 指针并不需要回退（因为 left 数组是升序的）依旧往右移动直到left[cur1]<=2*rightlcur2］。不断重复这样的过程，就能够求出所有左右端点分别位于两个子数组的翻转对数目。
由于两个指针最后都是不回退的的扫描到数组的结尾，因此两个有序序列求出翻转对的时间复杂度是O（N）。
综上所述，我们可以利用归并排序的过程，将求一个数组的翻转对转换成求左数组的翻转对数量＋右数组中翻转对的数量+左右数组合并时翻转对的数量。

降序版本：
 

class Solution {
public:vector<int> tmp;int reversePairs(vector<int>& nums) {tmp.resize(nums.size());    return MergeSort(nums,0,nums.size()-1);}int MergeSort(vector<int>& nums, int left, int right){if(left>=right)return 0;int mid = (left + right)>>1;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){while(cur2 <= right && nums[cur2]>=nums[cur1]/2.0)cur2++;if(cur2>right)break;ret += right - cur2 + 1;cur1++;}cur1 = left,cur2 = mid+1,i=0;while(cur1 <= mid & cur2 <= right){if(nums[cur1]<=nums[cur2]){tmp[i++] = nums[cur2++]; }else {tmp[i++] = nums[cur1++];}}while(cur1 <= mid){ret += right-cur2+1;tmp[i++] = nums[cur1++];}while(cur2 <= right){tmp[i++] = nums[cur2++]; }//还原for(int i = left;i<=right;i++)nums[i] = tmp[i-left];return ret;}
};