看到大家都是使用归并排序,我这里就加上树状数组的写法吧。
这里没有细节考虑值相同的问题(虽然题目中指明不会出现重复的数)
class Solution { public: long long ans = 0; int n; int C[200005] = {0}; struct point{ int val,pos; } a[200005]; int lowbit(int x){ return x&(-x); } static bool cmp(point x,point y){ return x.val < y.val; } void add(int x){ while(x <= n){ C[x]++; x+=lowbit(x); } } int sum(int x){ int tol = 0; while(x > 0){ tol+=(C[x]); x-=lowbit(x); } return tol; } int InversePairs(vector<int> data){ n = data.size(); for(int i = 1;i <= n;i++){ a[i].val = data[i-1]; a[i].pos = i; } sort(a+1,a+n+1,cmp); for(int i = 1;i <= n;i++){ add(a[i].pos); ans+=(i-sum(a[i].pos)); } return ans%1000000007; } };