1. 题⽬链接：493.翻转对
2. 题⽬描述：
题⽬解析：
翻转对和逆序对的定义⼤同⼩异，逆序对是前⾯的数要⼤于后⾯的数。⽽翻转对是前⾯的⼀个数要 ⼤于后⾯某个数的两倍。因此，我们依旧可以⽤归并排序的思想来解决这个问题。
3. 解法（归并排序）：
算法思路：
⼤思路与求逆序对的思路⼀样，就是利⽤归并排序的思想，将求整个数组的翻转对的数量，转换成 三部分：左半区间翻转对的数量，右半区间翻转对的数量，⼀左⼀右选择时翻转对的数量。重点就 是在合并区间过程中，如何计算出翻转对的数量。
与上个问题不同的是，上⼀道题我们可以⼀边合并⼀遍计算，但是这道题要求的是左边元素⼤于右 边元素的两倍，如果我们直接合并的话，是⽆法快速计算出翻转对的数量的。
例如left=[4,5,6] right=[3,4,5]时，如果是归并排序的话，我们需要计算left数组中有多少个 能与3组成翻转对。但是我们要遍历到最后⼀个元素6才能确定，时间复杂度较⾼。
因此我们需要在归并排序之前完成翻转对的统计。
下⾯依旧以⼀个⽰例来模仿两个有序序列如何快速求出翻转对的过程：
假定已经有两个已经有序的序列left=[4,5,6] right=[1,2,3]。
⽤两个指针cur1 cur2遍历两个数组。
◦ 对于任意给定的left[cur1]⽽⾔，我们不断地向右移动cur2，直到left[cur1]<=2* right[cur2]。此时对于right数组⽽⾔，cur2之前的元素全部都可以与left[cur1]构成翻转对。
◦ 随后，我们再将cur1向右移动⼀个单位，此时cur2指针并不需要回退（因为left数组是升序 的）依旧往右移动直到left[cur1]<=2*right[cur2]。不断重复这样的过程，就能够求出所有 左右端点分别位于两个⼦数组的翻转对数⽬。
由于两个指针最后都是不回退的的扫描到数组的结尾，因此两个有序序列求出翻转对的时间复杂度 是O(N)。
综上所述，我们可以利⽤归并排序的过程，将求⼀个数组的翻转对转换成求左数组的翻转对数量+ 右数组中翻转对的数量+左右数组合并时翻转对的数量。
降序版本
C++算法代码：
class Solution
{
int tmp[50010];
public:
int reversePairs(vector<int>& nums)
{
return mergeSort(nums, 0, nums.size() - 1);
}
int mergeSort(vector<int>& nums, int left, int right)
{
if (left >= right) return 0;
int ret = 0;
// 1. 先根据中间元素划分区间
int mid = (left + right) >> 1;
// [left, mid] [mid + 1, right]
// 2. 先计算左右两侧的翻转对
ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
// 3. 先计算翻转对的数量
int cur1 = left, cur2 = mid + 1, i = left;
while (cur1 <= mid) // 降序的情况
{
while (cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;
if (cur2 > right)
break;
ret += right - cur2 + 1;
cur1++;
}
// 4. 合并两个有序数组
cur1 = left, cur2 = mid + 1;
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;
}
};
Java算法代码：
class Solution
{
int[] tmp;
public int reversePairs(int[] nums)
{
int n = nums.length;
tmp = new int[n];
return mergeSort(nums, 0, n - 1);
}
public int mergeSort(int[] nums, int left, int right)
{
if (left >= right) return 0;
int ret = 0;
// 1. 根据中间元素，将区间分成两部分
int mid = (left + right) / 2;
// [left, mid] [mid + 1, right]
// 2. 求出左右两个区间的翻转对
ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
// 3. 处理⼀左⼀右 - 先计算翻转对
int cur1 = left, cur2 = mid + 1, i = left;
// 降序版本
while (cur1 <= mid)
{
while (cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;
if (cur2 > right)
break;
ret += right - cur2 + 1;
cur1++;
}
// 4. 合并两个有序数组
cur1 = left; cur2 = mid + 1;
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;
}
}
升序版本
C++算法代码：
class Solution
{
int tmp[50010];
public:
int reversePairs(vector<int>& nums)
{
return mergeSort(nums, 0, nums.size() - 1);
}
int mergeSort(vector<int>& nums, int left, int right)
{
if (left >= right) return 0;
int ret = 0;
// 1. 先根据中间元素划分区间
int mid = (left + right) >> 1;
// [left, mid] [mid + 1, right]
// 2. 先计算左右两侧的翻转对
ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
// 3. 先计算翻转对的数量
int cur1 = left, cur2 = mid + 1, i = left;
while (cur2 <= right) // 升序的情况
{
while (cur1 <= mid && nums[cur2] >= nums[cur1] / 2.0) cur1++;
if (cur1 > mid)
break;
ret += mid - cur1 + 1;
cur2++;
}
// 4. 合并两个有序数组
cur1 = left, cur2 = mid + 1;
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;
}
};
Java算法代码：
class Solution
{
int[] tmp;
public int reversePairs(int[] nums)
{
int n = nums.length;
tmp = new int[n];
return mergeSort(nums, 0, n - 1);
}
public int mergeSort(int[] nums, int left, int right)
{
if (left >= right) return 0;
int ret = 0;
// 1. 根据中间元素，将区间分成两部分
int mid = (left + right) / 2;
// [left, mid] [mid + 1, right]
// 2. 求出左右两个区间的翻转对
ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
// 3. 处理⼀左⼀右 - 先计算翻转对
int cur1 = left, cur2 = mid + 1, i = left;
// 升序版本
while (cur2 <= right)
{
while (cur1 <= mid && nums[cur2] >= nums[cur1] / 2.0) cur1++;
if (cur1 > mid)
break;
ret += mid - cur1 + 1;
cur2++;
}
// 4. 合并两个有序数组 - 升序
cur1 = left; cur2 = mid + 1;
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;
}
}