《算法题讲解指南：优选算法-分治-归并》--49.计算右侧小于当前元素的个数，50.翻转对
🔥小叶-duck：个人主页
❄️个人专栏：《Data-Structure-Learning》
《C++入门到进阶&自我学习过程记录》《算法题讲解指南》--优选算法
✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游
目录
49.计算右侧小于当前元素的个数
题目链接：
315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）
题目描述：
题目示例：
解法(归并排序)：
算法思路：
这一道题的解法与 求数组中的逆序对 的解法是类似的，但是这一道题要求的不是求总的个数，而是要返回一个数组，记录每一个元素的右边有多少个元素比自己小。
但是在我们归并排序的过程中，元素的下标是会跟着变化的，因此我们需要一个辅助数组，来将数组元素和对应的下标绑定在一起归并，也就是再归并元素的时候，顺势将下标也转移到对应的位置上。
由于我们要快速统计出某一个元素后面有多少个比它小的，因此我们可以利用求逆序对的第二种方法。
C++算法代码：
class Solution { public: vector<int> counts; vector<int> index; //记录nums中当前元素的原始下标 vector<int> tmp; vector<int> tmpi; //临时记录合并后对应元素位置变化下标随之变化的数组(保证元素和原始下标始终绑定) vector<int> countSmaller(vector<int>& nums) { counts.resize(nums.size()); index.resize(nums.size()); tmp.resize(nums.size()); tmpi.resize(nums.size()); //初始化index，使得nums每个元素下标和index一一对应 for(int i = 0; i <nums.size(); i++) { index[i] = i; } mergesort(nums, 0, nums.size() - 1); return counts; } void mergesort(vector<int>& nums, int left, int right) { if(left == right) { return; } int mid = (right - left) / 2 + left; mergesort(nums, left, mid); mergesort(nums, mid + 1, right); int cur1 = left, cur2 = mid + 1, i = 0; while(cur1 <= mid && cur2 <= right) { if(nums[cur1] > nums[cur2]) { counts[index[cur1]] += right - cur2 + 1; //重点 //因为index[cur1]始终是cur1当前元素的原始下标，所以不管当前元素位置怎么变化 //counts[index[cur1]]的位置都不会变 tmpi[i] = index[cur1]; tmp[i++] = nums[cur1++]; } else { tmpi[i] = index[cur2]; tmp[i++] = nums[cur2++]; } } while(cur1 <= mid) { tmpi[i] = index[cur1]; tmp[i++] = nums[cur1++]; } while(cur2 <= right) { tmpi[i] = index[cur2]; tmp[i++] = nums[cur2++]; } for(int j = left; j <= right; j++) { nums[j] = tmp[j - left]; index[j] = tmpi[j - left]; } } };算法总结及流程解析：
50.翻转对
题目链接：
493. 翻转对 - 力扣（LeetCode）
题目描述：
题目示例：
题目解析：
翻转对和逆序对的定义大同小异，逆序对是前面的数要大于后面的数。而翻转对是前面的一个数要大于后面某个数的两倍。因此，我们依旧可以用归并排序的思想来解决这个问题。
解法(归并排序)：
算法思路：
大思路与求逆序对的思路一样，就是利用归并排序的思想，将求整个数组的翻转对的数量，转换成三部分：左半区间翻转对的数量，右半区间翻转对的数量，一左一右选择时翻转对的数量。重点就是在合并区间过程中，如何计算出翻转对的数量。
与上个问题不同的是，上一道题我们可以一边合并一遍计算，但是这道题要求的是左边元素大于右边元素的两倍，如果我们直接合并的话，是无法快速计算出翻转对的数量的。
因此我们需要在归并排序之前完成翻转对的统计。
class Solution { public: vector<int> tmp; int count = 0; int reversePairs(vector<int>& nums) { tmp.resize(nums.size()); mergesort(nums, 0, nums.size() - 1); return count; } void mergesort(vector<int>& nums, int left, int right) { if(left >= right) { return; } int mid = (right - left) / 2 + left; mergesort(nums, left, mid); mergesort(nums, mid + 1, right); //这里需要注意：当我们左右区间排完序后，按照之前逆序对类似题目 //我们是求值和合并数组同时进行的 //因为左边大于右边正好就可以求值顺带可以进行合并操作 //但是这里求助的条件是左边需要大于右边的两倍 //也就是说如果左边大于右边我们不一定能够求值，但是必须要进行合并，就会出现问题 //所以如果不能同时进行操作我们就将求值和合并分开操作：先进行求值再进行合并数组 int cur1 = left, cur2 = mid + 1; while(cur1 <= mid && cur2 <= right)//降序操作 { //当左边大于右边的两边才会进行求值 if(nums[cur1] > (long long)2 * nums[cur2]) { count += right - cur2 + 1; cur1++; } else { cur2++; } }//当出了循环说明要么cur1>mid要么cur2>right，不管哪种情况此时翻转对是求完了 //无需像合并数组那样处理剩余部分 cur1 = left; cur2 = mid + 1; int i = 0; while(cur1 <= mid && cur2 <= right) { if(nums[cur1] > nums[cur2]) { tmp[i++] = nums[cur1++]; } else { tmp[i++] = nums[cur2++]; } } while(cur1 <= mid) { tmp[i++] = nums[cur1++]; } while(cur2 <= right) { tmp[i++] = nums[cur2++]; } // while(cur1 <= mid && cur2 <= right)//升序操作同样如此 // { // 当左边大于右边的两边才会进行求值 // if(nums[cur1] > (long long)2 * nums[cur2]) // { // count += mid - cur1 + 1; // cur2++; // } // else // { // cur1++; // } // } // cur1 = left; // cur2 = mid + 1; // int i = 0; // while(cur1 <= mid && cur2 <= right) // { // if(nums[cur1] > nums[cur2]) // { // tmp[i++] = nums[cur2++]; // } // else // { // tmp[i++] = nums[cur1++]; // } // } // 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]; } } };算法总结及流程解析：
结束语
到此，49.计算右侧小于当前元素的个数，50.翻转对 这两道算法题就讲解完了。49题通过维护原始下标数组，在归并过程中统计右侧较小元素数量；50题则需先统计满足条件的翻转对数量，再进行归并排序。希望大家能有所收获！
