​​​​​​【算法拾光】分治｜计算右侧小于当前元素的个数 + 翻转对

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */
#content_views .toc,
/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */
#content_views.markdown_views > p:empty:has(+ .toc),
#content_views.markdown_views > .toc + p:empty,
/* 富文本旧版目录标记 */
#content_views.htmledit_views #main-toc,
#content_views.htmledit_views #hr-toc,
#content_views.htmledit_views p[id*=\”-toc\”] {
display: none !important;
}
/* 目录去掉后，紧跟的首个标题不再多出一块上边距 */
#content_views.markdown_views > .toc + h1,
#content_views.markdown_views > .toc + h2,
#content_views.markdown_views > .toc + h3,
#content_views.markdown_views > .toc + h4,
#content_views.markdown_views > .toc + p:empty + h1,
#content_views.markdown_views > .toc + p:empty + h2,
#content_views.markdown_views > .toc + p:empty + h3,
#content_views.markdown_views > .toc + p:empty + h4 {
margin-top: 0 !important;
}

题目 1：计算右侧小于当前元素的个数

题目链接：315. 计算右侧小于当前元素的个数 – 力扣（LeetCode）

题目分析

给你一个整数数组 nums，按要求返回一个新数组 counts。counts[i] 表示在 nums[i] 的右侧，比 nums[i] 小的元素的数量。 暴力做法双层循环 \\(O(n^2)\\)，大数据直接超时。可以借助归并排序分治思想，在合并有序区间的时候统计答案。

注意：排序会打乱原数组下标，所以不能只存数值，要保存数值 + 原始下标，保证统计结果放到正确位置。

算法原理

分治思路和逆序对非常相似：

代码编写

vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n, 0);
vector<pair<int,int>> arr(n);
for(int i = 0; i < n; i++) arr[i] = {nums[i], i};
vector<pair<int,int>> temp(n);
mergeSort(arr, temp, ans, 0, n – 1);
return ans;
}

void mergeSort(vector<pair<int,int>>& arr, vector<pair<int,int>>& temp, vector<int>& ans, int l, int r) {
if(l >= r) return;
int mid = l + (r – l) / 2;
mergeSort(arr, temp, ans, l, mid);
mergeSort(arr, temp, ans, mid + 1, r);
int i = l, j = mid + 1, k = l;
while(i <= mid && j <= r) {
if(arr[i].first <= arr[j].first) {
temp[k++] = arr[i++];
} else {
// arr[i] > arr[j]，i~mid全部都大于arr[j]
ans[arr[i].second] += r – j + 1;
temp[k++] = arr[j++];
}
}
while(i <= mid) temp[k++] = arr[i++];
while(j <= r) temp[k++] = arr[j++];
for(int p = l; p <= r; p++) arr[p] = temp[p];
}

题目 2：翻转对

题目链接：493. 翻转对 – 力扣（LeetCode）

题目分析

给定一个数组 nums，如果 i < j 且 nums[i] > 2 * nums[j]，称 (i,j) 为一组翻转对。求翻转对总数量。 和逆序对的区别：判断条件不是 nums[i] > nums[j]，而是 nums[i] > 2 * nums[j]。 同样归并分治，但是统计翻转对和合并有序数组要分成两轮循环，不能在合并的时候一起统计，不然逻辑会出错。

算法原理

代码编写

vector<int> temp;
int reversePairs(vector<int>& nums) {
temp.resize(nums.size());
return mergeSort(nums, 0, nums.size() – 1);
}

int mergeSort(vector<int>& nums, int l, int r) {
if(l >= r) return 0;
int mid = l + (r – l) / 2;
int res = mergeSort(nums, l, mid) + mergeSort(nums, mid + 1, r);

// 第一步：单独统计翻转对
int i = l, j = mid + 1;
while(i <= mid) {
while(j <= r && (long long)nums[i] > 2LL * nums[j]) {
j++;
}
res += j – (mid + 1);
i++;
}

// 第二步：归并合并
i = l, j = mid + 1;
int k = l;
while(i <= mid && j <= r) {
if(nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
while(i <= mid) temp[k++] = nums[i++];
while(j <= r) temp[k++] = nums[j++];
for(int p = l; p <= r; p++) nums[p] = temp[p];
return res;
}

本篇总结

这两道题都是归并分治的进阶题型，和逆序对一脉相承：