假设我们有一个数组，在这个数组中，如果满足以下条件，我们将说一对（A [i]和A [j]）为重要的反向对-
如果i <j并且A [i]> 2 * nums [j]
我们必须找到重要反向对的数量。因此，如果输入类似于[2,8,7,7,2]，则结果将为3。
为了解决这个问题，我们将遵循以下步骤-
回答：= 0
定义一个函数merge()，将采用一个数组，低，中，高，
k：=高-低+ 1
定义大小为k的数组温度
i：=低，j =中+ 1，k：= 0
第一：=中+ 1
当我<=中时，做-
temp [k]：= a [j]
（将j增加1）
（将k增加1）
（先增加1）
而first <=高且a [first] * 2 <a，则执行-
而（j <=高且a [j] <= a [i]），则-
ans：= ans + first-（mid + 1）
temp [k]：= a [i]
（将i增加1）
（将k增加1）
当j <=高时，做-
temp [k]：= a [j]
（将k增加1）
（将j增加1）
k：= 0
对于初始化i：=低，当i <=高时，更新（将i增加1），请执行-
a [i]：= temp [k]
（将k增加1）
定义一个函数calc()，将采用一个数组，低，高，
如果低> =高，则-
返回
中：=低+（高-低）/ 2
调用函数calc(a,low,mid)
调用函数calc（a，mid + 1，high）
调用函数merge(a,low,mid,high)
定义一个函数solve()，它将采用数组A，
回答：= 0
n：= A的大小
调用函数calc(A,0,n-1)
返回ans
在主要方法中，执行以下操作
返回调用函数solve(nums)
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int ans = 0;
void merge(vector <int> &a, lli low, lli mid, lli high){
lli k = high - low + 1;
vector <lli> temp(k);
lli i = low, j = mid + 1;
k = 0;
lli first = mid + 1;
while(i <= mid){
while(first <= high && (lli)a[first] * 2 < (lli)a[i]) {
first++;
}
while(j <= high && a[j] <= a[i])
{
temp[k] = a[j];
j++;
k++;
}
ans += first - (mid + 1);
temp[k] = a[i];
i++;
k++;
}
while(j <= high){
temp[k] = a[j];
k++;
j++;
}
k = 0;
for(lli i = low; i <= high; i++){
a[i] = temp[k];
k++;
}
}
void calc(vector <int> &a, lli low, lli high){
if(low >= high)return;
lli mid = low + (high - low)/2;
calc(a, low, mid);
calc(a, mid + 1, high);
merge(a, low, mid, high);
}
lli solve(vector<int> &A) {
ans = 0;
lli n = A.size();
calc(A, 0, n - 1);
return ans;
}
int reversePairs(vector<int>& nums) {
return solve(nums);
}
};
main(){
Solution ob;
vector<int> v = {2,8,7,7,2};
cout << (ob.reversePairs(v));
}{2,8,7,7,2}输出结果
3