---

題目鏈接：

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