AcWing 65. 数组中的逆序对
原题链接
困难
作者:
linux_2019
,
2019-09-10 10:38:17
,
所有人可见
,
阅读 786
C++ 代码
class Solution {
public:
int cnt;
void merge(vector<int> &a,int l,int mid,int r)
{
vector<int> b;
int i=l,j=mid+1;
for(int k=l;k<=r;k++)
if(j>r|| i<=mid&&a[i]<a[j])
b.push_back(a[i++]);
else
b.push_back(a[j++]),cnt+=mid+1-i;
for(int k=l;k<=r;k++)
a[k]=b[k-l];
}
void merge_sort(vector<int> &a,int l,int r)
{
if(l>=r)
return;
int mid=l+r >>1;
merge_sort(a,l,mid);
merge_sort(a,mid+1,r);
merge(a,l,mid,r);
}
int inversePairs(vector<int>& nums) {
cnt=0;
merge_sort(nums,0,nums.size()-1);
return cnt;
}
};