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

---

题目链接：

493. 翻转对

---

题目描述：

---

解法

分治

策略一：计算当前元素cur1后面，有多少元素的两倍比我cur1小（降序）

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

策略二：计算当前元素cur2之前，有多少元素的一半比我cur2大（升序）

最后合并两个有序数组。

---

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 < j 且 nums[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