分治算法之归并排序
每日激励：“不设限和自我肯定的心态：I can do all things。 — Stephen Curry”
绪论：
本章将学习分治算法，将通过练习促学习的方式来学习，主要通过先从归并算法开始带你打好基础，后续三道困难题都将在这个排序的基础上进行扩展，利用归并的思想来解决，在排序的过程中快速查找在自己后面的比自己小的值（降序排序），以及在自己前面比自己大的值（升序排序），具体细节让我们见文章吧，。
————————
早关注不迷路，话不多说安全带系好，发车啦（建议电脑观看）。
分治（归并排序）
具体训练：
1. 归并排序
题目：
归并排序的核心思想：
- 根据中间的mid分成两部分：
- 先排左边：内部有是一个归并，当数组只有一个值时返回
- 再拍右边：内部同样是一个归并，当数组只有一个值时返回
- 将左右两个数组合并成一个有序数组返回
class Solution {
public:vector<int> tmp;vector<int> sortArray(vector<int>& nums) {msort(nums,0,nums.size()-1);return nums;}//Merge Sortvoid msort(vector<int>& nums,int left,int right){if(left >= right) return ;int mid = left + (right - left) / 2;//mid 1 2 3 4 mid = 1// 2 3 mid msort(nums,left,mid);msort(nums,mid+1,right);//left ~ mid - 1//mid ~ righttmp.clear();int cur1 = left,cur2 = mid + 1;while(cur1 <= mid && cur2 <= right){if(nums[cur1] < nums[cur2]) tmp.push_back(nums[cur1++]);else tmp.push_back(nums[cur2++]);}//处理剩下的while(cur1 <= mid){tmp.push_back(nums[cur1++]);//处理剩下的}while(cur2 <= right){tmp.push_back(nums[cur2++]);}for(int i = left;i <= right;i++)nums[i] = tmp[i - left];}
};
其中本质就是后序遍历的方法：先遍历左，左边结束后才到右，最后到结点：
快排是每一层选择一个基准元素key，然后进行分组后重复，直到数组分成一个元素时分组结束
而快排就相当于一种前序遍历，处理完结点后分成两组后再分别处理：
本质区别就是处理数组时机不同
2. 交易逆序对的总数
题目：
分析题目
对于暴力解法来说：比较简单两层暴力枚举即可找到最多的逆序对（但一定是会超时的）
优化方法：
上图描述：
- 首先将一整个区间划分成两部分 a、b
- 然后在新区域a、b中找逆序对，得到a、b个
- 然后再将 a、b区域联合起来看，选择一个a区域中的逆序对，然后再选择一个b区域的，最终组合成新的逆序对，个数为c
- 那么最终逆序对个数为 a + b + c
顺序是：先挑a区域、再挑b区域、最后查询 a 和 b 组合（左半部分、右半部分、一左一右）
那么再次优化，先找左半部分，找完后进行排序、同理找完右半部分，进行排序，最后一左一右（因为排序后找一左一右就有单调性了就能快速的确定个数！）
最终：本质就很归并排序是一样的了！！（如下图）
其中对合并排序和其中需要的其他操作来找结果的详细解释（如下图）：
当到达归并排序的某一层时的操作：
- 首要目的是为了合并，但同时也要记录逆序对的个数！
- 回顾个数的计算：a（左） + b（右） + c（左右），其中a、b在上一层已经计算了，所以本层只用计算 c 即可
- 记录个数（c 一左一右）：那么也就是要找 cur1 后面能接的 cur2（记住）
- 回到公式当 num[cur1] <= num[cur2] 时就正常进行归并排序，cur1++
- 而当 num[cur1] > num[cur2] 时，这时cur1即往后的值都是大于cur2的（因为a区间是始终升序的），所以个数就能直接增加 ret += mid - cur1 + 1个，然后进行正常归并排序步骤cur2++
题目核心逻辑
class Solution {
public:int reversePairs(vector<int>& record) {return mergesort(record,0,record.size()-1);}//归并int mergesort(vector<int>& record,int left,int right){if(left >= right) return 0;int mid = left + (right - left) / 2;int a = mergesort(record,left,mid);int b = mergesort(record,mid+1,right);vector<int> temp;// cint c= 0;//进行归并，此处是升序，取出小的放入容器中int cur1 = left,cur2 = mid+1;while(cur1 <= mid & cur2 <= right){//策略1：找前面有多少大的，针对cur2来看if(record[cur1] > record[cur2]){c += mid - cur1 + 1;temp.push_back(record[cur2]);cur2++;}else{//cur1 <= cur2temp.push_back(record[cur1]);cur1++;}}while(cur1 <= mid) temp.push_back(record[cur1++]);while(cur2 <= right) temp.push_back(record[cur2++]);for(int j = left; j <= right; j++)record[j] = temp[j - left];return a + b + c;}};
3. 计算右侧小于当前元素的个数
题目：
分析题目
分析题目和例1：
-
找当前这个数的右边有多少比自己小的
所以就和上题比较像，可以使用
上一题中的第二个策略：找当前元素后边有多少个比我小（前提降序） -
在降序的前提下（这里的降序，本质就是在归并排序中执行的排序操作）
-
排序后就是内部的一些问题，同样的也是 左区间 + 右区间 + 左右区间
-
其中具体已经在上题中说明了，本题主要还是讲解左右区间：
-
通过比较cur1、cur2找到比自己小的元素，具体公式如下图
-
本题需要返回的是一个数组nums，其中它对应的是，它上方数值右边比他小的个数
-
当cur1 > cur2时，因为是降序cur2右边都将比他小，所以就直接加上right - cur2 - 1
如何处理当排序后其索引改变导致找不到原数据的问题
- 那么其中就会有一个问题，当排完序后如何仍然找到对应的原始的下标呢（因为排完序后位置就发生了改变，低下记录值的数组nums就将不再对应上，所以就需要进行一定的处理）
- 一般来说可以使用hash的kv进行绑定值和下标，但本题可能会出现重复的值所以就不适合使用
- 那么可以使用一个index新数组进行绑定管理索引，其中在操作nums的同时index也是同样的改变
- 这样index数组中的索引就始终对应了
题目核心逻辑
本题重点：
- 通过新增一个start_index索引数组来记录当前索引的位置
- 并且在更改位置的过程中记录当前索引的位置，然后实时的也进行修改
- 其中也多借助了一个index辅助数组进行存储移动前的索引的位置
class Solution {
public:vector<int> countSmaller(vector<int>& nums) {int n = nums.size();//归并排序vector<int> res(n);vector<int> start_index(n);for(int i = 0;i < nums.size();i++)start_index[i] = i;mergeSort(nums,res,start_index,0,n - 1);return res;}int temp[100010] = {};int index[100010] = {};void mergeSort(vector<int>& nums,vector<int>& res,vector<int>& start_index,int left,int right){if(left >= right) return ;//当超过范围就返回int mid = (right + left) / 2;//取中进行划分mergeSort(nums,res,start_index,left,mid);mergeSort(nums,res,start_index,mid+1,right);//a + b，合并的同时进行计算int p1 = left,p2 = mid + 1,ti = 0;while( p1 <= mid && p2 <= right){//降序，等于 在归并排序中本质放到哪里都行，但在本题需要找的是 p1 > p2 的才个数，所以将 等于 放到 < 处if(nums[p1] <= nums[p2]){index[ti] = start_index[p2];//存储他的下标temp[ti++] = nums[p2++]; }else{//记录长度//start_index是他的原始索引位置res[start_index[p1]] += right - p2 + 1;index[ti] = start_index[p1];//存储他的下标temp[ti++] = nums[p1++];}}while(p1 <= mid) {res[start_index[p1]] += right - p2 + 1;index[ti] = start_index[p1];//存储他的下标temp[ti++] = nums[p1++];}while(p2 <= right) {index[ti] = start_index[p2];//存储他的下标temp[ti++] = nums[p2++]; }//将temp放入数组for(int i = left;i <= right ;i++){start_index[i] = index[i - left];//让原数位置也跟着移动nums[i] = temp[i - left];//移动值的同时移动index//num[i]是新值，i是新}}};
4. 翻转对
题目：
分析题目
- 分析题目：找出所有值是后面值的两倍的的个数
- 如下图：3 > 1*2 共有两次所以也就是2
那么类似的还是找比自己小的元素，只不过此时是小两倍的元素，就会导致运算情况和归并并不一样了
此时就需要将算左 右区间的情况单独出来看，用一个双指针的方式（这里就不过诉了看下图）来提前处理排好序的值，找到左 右区间合起来看时有多少符合翻转对的值，具体为什么不能放到归并中操作下述代码中已经注释 - 一个基础的单调性双指针算法（有问题可以评论）
题目核心逻辑
- 具体细节写在注释
class Solution {
public:int reversePairs(vector<int>& nums) {return mergeSort(nums,0,nums.size()-1);}int tmpNums[50010];int mergeSort(vector<int>& nums, int left, int right) {if (left >= right)return 0;int mid = (left + right) / 2;int ret = 0;// [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) // 降序排序{//主要不同就是在这里，不能再归并中同时处理就是因为，可能会跳过处理某些情况//若：当cur1 > cur2 时会不断的走cur1的而不会动 cur2，这样就会导致 cur1 > 2*cur2 其中的cur2不变导致 ret 无法遍历所有情况if (nums[cur1] >(long long) 2*nums[cur2]) {cur1++;ret += right - cur2 + 1;} else {cur2++;}}cur1 = left, cur2 = mid + 1;//恢复值//不放在一起的原因是，他们运算的过程不一致，主要体现在 nums[cur1] > 2*num[cur2] 时才需要记录答案，这里有许多细节//并不好叙述，主要就是理解他们 运算是不一样的 会导致某些问题的方式从而让 cur2 和 cur1 的比较并不正常（具体如上描述）while (cur1 <= mid && cur2 <= right) // 降序排序{if (nums[cur1] <= nums[cur2]) {tmpNums[i++] = nums[cur2++];} else {tmpNums[i++] = nums[cur1++];}}// 4. 处理剩余的排序⼯作while (cur1 <= mid) {tmpNums[i++] = nums[cur1++];}while (cur2 <= right) {tmpNums[i++] = nums[cur2++];}for (int j = left; j <= right; j++) {nums[j] = tmpNums[j - left];}return ret;}
};