题意：给定一个数组nums，求若 i<j and nums[i] > 2*nums[j] 的逆序对。
Note: 数组的长度不会超过50，000
不愧是hard模式的题目，虽然已经知道可以用归并排序来做，但是写出来的答案总有问题，真的是暴风哭泣 :(
一直在找bug，最后发现是我写的merge函数有问题，分析一下：
这是我一开始写的错误的merge函数，我是在 aux[i] > aux[j] 里面加入了若也满足 aux[i] > 2*aux[j] 来计算res
int merge(vector<int>& arr, vector<int>& aux, int l, int mid, int r){
for(int i=l;i<=r;i++){
aux[i] = arr[i];
}
int res = ; //统计逆序对数量
int i = l, j = mid+;
for(int k=l; k<=r;k++){
if(i>mid){
arr[k] = aux[j];
j++;
}
else if(j>r){
arr[k] = aux[i];
i++;
}
else if(aux[i]<aux[j]){
arr[k] = aux[i];
i++;
}
else{
arr[k] = aux[j];if(aux[i] > *aux[j])
res+=(mid-i+);
j++;
}
}
return res;
}我一直不知道自己的解法为什么不对，然后参考了别人的解法，改了一下merge函数。
我觉得错误的地方是把 if(aux[i] > 2*aux[j]) 这个语句放在了 aux[i] > aux[j] 里 ，只有当同时满足这两个条件时res才会增加，但是若不满足2倍的大于关系时，j++ , 这样就会丢掉一些解。所以要把它拿出来另外判断！
正确解法如下：
class Solution {
public:
int mergeSort(vector<int>& nums, vector<int>& aux, int l, int r){
if(l >= r) return ;
int mid = (l+r)/; //(l+r)>>1
int left = mergeSort(nums, aux, l, mid);
int right = mergeSort(nums, aux, mid+,r);
int pair = left + right + merge(nums, aux, l, mid, r);
return pair;
}
int merge(vector<int>& arr, vector<int>& aux, int l, int mid, int r){
for(int i=l;i<=r;i++){
aux[i] = arr[i];
}
int res = ; //统计逆序对数量
int i = l, j = mid+;
for(int k=l; k<=r;k++){
if(i>mid){
arr[k] = aux[j];
j++;
}
else if(j>r){
arr[k] = aux[i];
i++;
}
else if(aux[i]<aux[j]){
arr[k] = aux[i];
i++;
}
else{
arr[k] = aux[j];
j++;
}
}
/* for(int s=l,t=mid+1;s<=mid;s++){
while(t<=r && aux[s] > 2LL*aux[t]){
res += mid-s+1;
t++;
}
}
*/
for(int s=l,t=mid;s<=mid;s++){
while(t+<=r && aux[s] > 2LL*aux[t+]) t++;
res += t-mid; // t-(mid+1)+1 = t-mid
}
return res;
}
int reversePairs(vector<int>& nums) {
int n = nums.size();
if(n==) return ;
vector<int> aux(nums);
return mergeSort(nums, aux, , n-);
}
};hard模式 真是不容易 == 刷题真难