> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。
> 目标：熟练掌握分治归并算法。
> 毒鸡汤：学习，学习，再学习 ! 学，然后知不足。
> 专栏选自：刷题训练营
> 望小伙伴们点赞👍收藏✨加关注哟💕💕
🌟前言分析
最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题，而我们刷题的官网可以参考：
⭐知识讲解
基本思想：
这个算法在我们学习数据结构中八大排序之归并，如果大家对这个算法比较陌生的话，可以参考下面这篇博客：
数据结构：手撕各种排序
特点：
我们下面题目所采用的方法都是三路划分法思想，这也和我们的标题分治不谋而合。
大致做题流程：
做题前一定要先画图，在写代码，如果能自己画出图来写代码轻松不少。
🌙topic-->1
题目链接：1. 排序数组
题目分析：
给你一个整数数组 nums，请你将该数组升序排列。（在上一个板块我们采用了快排算法解决，这里采用归并算法来解决）
算法原理：
- 解法：采用归并算法
图解：
细节处理：
- 递归结束标志
- 合并数组循环结束标志
- 处理没有遍历完的数组
代码演示：
class Solution { vector<int> tmp; public: vector<int> sortArray(vector<int>& nums) { // 开辟一个新的数组 tmp.resize(nums.size()); // 调用归并 mergeSort(nums, 0, nums.size() - 1); // 返回 return nums; } void mergeSort(vector<int>& nums, int left, int right) { if(left >= right) return;// 递归结束标志 // 1.选择中间点划分区域 [left, mid] [mid+1, right] int mid = (left + right) >> 1; // 2.把左右区间排序(递归) mergeSort(nums, left, mid); mergeSort(nums, mid + 1, right); // 3.合并两个有序数组 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++]; // 4.还原数组 for(int i = left;i <= right; i++) nums[i] = tmp[i -left]; } };
🌙topic-->2
题目链接：2.LCR 170. 交易逆序对的总数
题目分析：
输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。
算法原理：
- 解法：采用归并算法
图解：
代码演示：
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; } };
🌙topic-->3
题目链接：3. 计算右侧小于当前元素的个数
题目分析：
给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
算法原理：
- 解法：采用归并算法
图解：
代码演示：
class Solution { vector<int> ret; vector<int> index; // 记录 nums 中当前元素的原始下标 int tmpNums[500010]; int tmpIndex[500010]; public: vector<int> countSmaller(vector<int>& nums) { int n = nums.size(); ret.resize(n); index.resize(n); // 初始化⼀下 index 数组 for (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++]; } } // 4. 处理剩下的排序过程 while (cur1 <= mid) { tmpNums[i] = nums[cur1]; tmpIndex[i++] = index[cur1++]; } while (cur2 <= right) { tmpNums[i] = nums[cur2]; tmpIndex[i++] = index[cur2++]; } for (int j = left; j <= right; j++) { nums[j] = tmpNums[j - left]; index[j] = tmpIndex[j - left]; } } };
🌙topic-->4
题目链接：4. 翻转对
题目分析：
给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。你需要返回给定数组中的重要翻转对的数量。
算法原理：
- 解法：采用归并算法
图解：
代码演示：
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 = left; while (cur1 <= mid) // 降序的情况 { while (cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++; if (cur2 > right) break; ret += right - cur2 + 1; cur1++; } // 4. 合并两个有序数组 cur1 = left, cur2 = mid + 1; while (cur1 <= mid && cur2 <= right) tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : 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]; return ret; } };
🌟结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
