【分治】翻转对
493. 翻转对
给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个*重要翻转对*。
你需要返回给定数组中的重要翻转对的数量。
示例 1:
输入: [1,3,2,3,1]
输出: 2示例 2:
输入: [2,4,3,5,1]
输出: 3注意:
- 给定数组的长度不会超过
50000。 - 输入数组中的所有数字都在32位整数的表示范围内。
解题思路：归并排序 + 双指针
这道题又是借鉴 剑指 Offer 51. 数组中的逆序对 的解题思路，其中两个思路都是可以的，也就是说升序和降序的情况都能解决这道题，因为这道题要找的是大于后面的，所以就 采用降序的思路，升序的思路可以自己尝试，只需要改改条件就能达到！
不过这道题不同的是，它的判断条件变成了 nums[i] > 2*nums[j]，如果我们在分治后合并的时候顺便处理的话，其实是不太方便的，因为合并的时候拷贝到临时数组的条件是只要大于或者小于等于一倍的条件即可，所以我们 单独把计算翻转对个数的事情拎出来！
这里计算翻转对，采用的是 双指针的思想，让 cur1 和 cur2 都不回退的往右走（自己结合降序情况分析为什么可以不回退，一直往右走）并且不断的判断是否有成立的区间，是的话则累加翻转对个数，直到两个指针有一个出界为止！
具体步骤如下图所示：
然后接着就是归并排序中的合并操作了，这个已经轻车熟路了，就不再赘述了！具体的参考下面代码：
class Solution {
private:
vector<int> tmp; // 辅助数组
public:
int reversePairs(vector<int>& nums) {
int n = nums.size();
tmp.resize(n);
return merge_sort(nums, 0, n - 1);
}
int merge_sort(vector<int>& nums, int left, int right)
{
if(left >= right)
return 0;
// 先分治
int ret = 0;
int mid = (left + right) >> 1;
ret += merge_sort(nums, left, mid);
ret += merge_sort(nums, mid + 1, right);
// 重点：在合并之前，利用双指针计算翻转对的数量（目前两个数组是降序的情况）
int cur1 = left, cur2 = mid + 1;
while(cur1 <= mid && cur2 <= right)
{
if((nums[cur1] / 2.0) <= nums[cur2]) // 不满足则让cur2往右走
cur2++;
else
{
ret += right - cur2 + 1; // 满足则累加满足条件的区间个数
cur1++;
}
}
// 处理完翻转对之后再合并两个有序数组
cur1 = left, cur2 = mid + 1;
int i = left;
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++];
// 最后拷贝到原数组中
while(left <= right)
{
nums[left] = tmp[left];
left++;
}
return ret;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-05-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
