leetCode 493 翻转对 归并分治 + 图解
493. 翻转对 - 力扣（LeetCode）
给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。你需要返回给定数组中的重要翻转对的数量。
- 求"小和"问题是，当我 j 来到一个位置的时候，你的左侧 i 去给我划答案
- 求"翻转对"问题是，当我 i 来到一个位置的时候，你的右侧 j 去给我划答案
class Solution {
public:int merge(vector<int>&arr, int left, int mid, int right) {int n = right - left + 1;//vector<int> help(n, 0);int* help = new int[n]();// 统计部分int ans = 0;for (int i = left, j = mid + 1; i <= mid; i++) {// 求"翻转对"问题是，当我i来到一个位置的时候，你的右侧j去给我划答案while (j <= right && (long)arr[i] > (long)arr[j] * 2) {j++;}ans += j - mid - 1;}// 正常mergeint i = 0,a = left, b = mid + 1;while (a <=mid && b <= right) help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];while (a <= mid) help[i++] = arr[a++];while (b <= right) help[i++] = arr[b++];for (int i = 0; i < n; i++) arr[i + left] = help[i];delete[] help;return ans;}// 统计left...right范围上，翻转对的数量，同时left...right范围上统计完后变有序int counts(vector<int>& arr, int left, int right) {if (left == right) return 0;// int mid = (left + right) / 2;int mid = left + ((right - left) >> 1);return counts(arr, left, mid) + counts(arr, mid + 1, right) + merge(arr, left, mid, right);}int reversePairs(vector<int> arr) {int n = arr.size();return counts(arr, 0, n - 1);}
};我的往期文章：
归并排序 图解 递归 + 非递归 + 笔记-CSDN博客
https://blog.csdn.net/weixin_41987016/article/details/134338789?spm=1001.2014.3001.5501 归并分治 归并排序的应用 + 图解 + 笔记-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/134340208?spm=1001.2014.3001.5501
归并排序 merge Sort + 图解 + 递归 / 非递归-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/134347278?spm=1001.2014.3001.5501参考和推荐视频：
算法讲解022【必备】归并分治_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1L14y1B7ef/?spm_id_from=333.788.recommend_more_video.0&vd_source=a934d7fc6f47698a29dac90a922ba5a3