C ++中的反向对
假设我们有一个数组，在这个数组中，如果满足以下条件，我们将说一对（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