欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 文旅 > 手游 > 【C++算法】50.分治_归并_翻转对

【C++算法】50.分治_归并_翻转对

2025/5/7 19:48:03 来源:https://blog.csdn.net/hlyd520/article/details/147053874  浏览:    关键词:【C++算法】50.分治_归并_翻转对

文章目录

    • 题目链接:
    • 题目描述:
    • 解法
    • C++ 算法代码:
    • 图解


题目链接:

493. 翻转对


题目描述:

e1a56c57c284100520d1840d3224460e


解法

分治

策略一:计算当前元素cur1后面,有多少元素的两倍比我cur1小(降序)

利用单调性使用同向双指针。

6ca12f25aadf9a660c566e1254f800d0

策略二:计算当前元素cur2之前,有多少元素的一半比我cur2大(升序)

8ae918bf3c685ed0b37605b78c2cc096

最后合并两个有序数组。


C++ 算法代码:

降序版本

class Solution 
{int tmp[50010];  // 临时数组,用于归并排序中合并两个子数组
public:// 主函数,计算数组中的翻转对数量int reversePairs(vector<int>& nums) {return mergeSort(nums, 0, nums.size() - 1);  // 调用归并排序函数}// 归并排序函数,返回区间[left, right]内的翻转对数量int mergeSort(vector<int>& nums, int left, int right){if(left >= right) return 0;  // 基本情况:如果区间只有一个元素或为空,翻转对数量为0int ret = 0;  // 保存翻转对数量// 1. 先根据中间元素划分区间int mid = (left + right) >> 1;  // 计算中间位置,相当于 (left + right) / 2// 2. 递归计算左右两侧的翻转对数量ret += mergeSort(nums, left, mid);       // 左半部分翻转对数量ret += mergeSort(nums, mid + 1, right);  // 右半部分翻转对数量// 3. 计算跨越左右两个子数组的翻转对数量int cur1 = left, cur2 = mid + 1;// 对于左子数组中的每个元素,计算右子数组中有多少元素可以构成翻转对while(cur1 <= mid) {// 在右子数组中查找第一个小于 nums[cur1]/2 的元素位置// 即满足 nums[cur2] < nums[cur1]/2 的最小的cur2while(cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;if(cur2 > right)  // 如果右子数组中所有元素都不满足条件break;// 右子数组中从cur2到right的所有元素都能与nums[cur1]构成翻转对ret += right - cur2 + 1;cur1++;  // 处理左子数组中的下一个元素}// 4. 合并两个有序子数组(降序合并)cur1 = left;cur2 = mid + 1;int i = left;  // 临时数组的起始索引// 比较左右子数组元素,较大者先放入临时数组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;  // 返回翻转对总数}
};

升序版本

class Solution 
{int tmp[50010];  // 临时数组,用于归并排序中合并两个子数组
public:// 主函数,计算数组中的翻转对数量int reversePairs(vector<int>& nums) {return mergeSort(nums, 0, nums.size() - 1);  // 调用归并排序函数}// 归并排序函数,返回区间[left, right]内的翻转对数量int mergeSort(vector<int>& nums, int left, int right){if(left >= right) return 0;  // 基本情况:如果区间只有一个元素或为空,翻转对数量为0int ret = 0;  // 保存翻转对数量// 1. 先根据中间元素划分区间int mid = (left + right) >> 1;  // 计算中间位置,相当于 (left + right) / 2// 2. 递归计算左右两侧的翻转对数量ret += mergeSort(nums, left, mid);       // 左半部分翻转对数量ret += mergeSort(nums, mid + 1, right);  // 右半部分翻转对数量// 3. 计算跨越左右两个子数组的翻转对数量int cur1 = left, cur2 = mid + 1;// 对于右子数组中的每个元素,计算左子数组中有多少元素可以构成翻转对while(cur2 <= right) {// 在左子数组中查找第一个大于 2*nums[cur2] 的元素位置// 即满足 nums[cur1] > 2*nums[cur2] 的最小的cur1while(cur1 <= mid && nums[cur2] >= nums[cur1] / 2.0) cur1++;if(cur1 > mid)  // 如果左子数组中所有元素都不满足条件break;// 左子数组中从cur1到mid的所有元素都能与nums[cur2]构成翻转对ret += mid - cur1 + 1;cur2++;  // 处理右子数组中的下一个元素}// 4. 合并两个有序子数组(升序合并)cur1 = left;cur2 = mid + 1;int i = left;  // 临时数组的起始索引// 比较左右子数组元素,较小者先放入临时数组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++];// 将临时数组中的元素复制回原数组for(int j = left; j <= right; j++)nums[j] = tmp[j];return ret;  // 返回翻转对总数}
};

图解

例如:nums = [1, 3, 2, 3, 1]

初始化:

  • 原始数组: [1, 3, 2, 3, 1]
  • 我们需要找到所有满足 i < jnums[i] > 2 * nums[j] 的索引对 (i, j)

第一层递归(整个数组):

  • [1, 3, 2, 3, 1] 分为 [1, 3][2, 3, 1]

处理左半部分 [1, 3]:

  • 进一步划分为 [1][3]
  • 这些是单个元素,不需要计算内部的翻转对
  • 计算跨越的翻转对: 没有跨越的翻转对(因为两个子数组只有一个元素)
  • 合并: [3, 1] (降序排序)

处理右半部分 [2, 3, 1]:

  • 进一步划分为 [2][3, 1]
  • 对于 [3, 1], 递归处理:
    • 划分为 [3][1]
    • 计算跨越的翻转对: 3 > 2*1, 所以有1个翻转对
    • 合并: [3, 1] (降序排序)
  • 计算跨越的翻转对([2] 和 [3, 1]):
    • 对于左子数组的元素2:
      • 检查右子数组的元素: 2 不大于 2*3, 但2 > 2*1
      • 所以有1个翻转对
  • 合并: [3, 2, 1] (降序排序)

最后合并 [3, 1][3, 2, 1]:

  • 计算跨越的翻转对:
    • 对于左子数组的元素3:
      • 检查右子数组的元素: 3 不大于 2*3, 3 不大于 2*2, 但3 > 2*1
      • 所以有1个翻转对
    • 对于左子数组的元素1:
      • 检查右子数组的元素: 1 不大于 2*3, 1 不大于 2*2, 1 不大于 2*1
      • 所以没有翻转对
  • 合并: [3, 3, 2, 1, 1] (降序排序)

计算翻转对总数:

  • 左半部分内部: 0个
  • 右半部分内部: 1+1=2个
  • 跨越左右半部分: 0个

因此,翻转对总数是 0 + 2 + 0 = 2 个。

这两个翻转对分别对应原数组中的:

  1. (1, 4): 索引1处的元素3 > 2*索引4处的元素1
  2. (3, 4): 索引3处的元素3 > 2*索引4处的元素1

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词