思路参考归并排序，在归并排序的同时统计逆序对。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
private:
long reverseNum;
vector<int>* data;
vector<int>* tdata;
public:
int InversePairs(vector<int> data) {
if(data.size()<=1) return 0;
this->data=&data;
reverseNum=0;
tdata=new vector<int>(data.size());
findInversePair(0,data.size()-1);
return (int)(reverseNum%1000000007);
}
void findInversePair(int left,int right){
if(left==right) return;
int mid=(right+left)/2;
findInversePair(left,mid);
findInversePair(mid+1,right);
for(int i=left;i<=right;i++) (*tdata)[i]=(*data)[i];
int pLeft=mid;
int pRight=right;
int pData=right;
while(pLeft>=left && pRight>=mid+1){
if((*tdata)[pLeft]>(*tdata)[pRight]){
reverseNum+=pRight-mid;
(*data)[pData]=(*tdata)[pLeft--];
}else{
(*data)[pData]=(*tdata)[pRight--];
}
pData--;
}
while(pLeft>=left) (*data)[pData--]=(*tdata)[pLeft--];
while(pRight>=mid+1) (*data)[pData--]=(*tdata)[pRight--];
}
};
|
其实统计的难度不是很大，关键是在于归并排序的算法。虽然我的思路基本是对的，但是结束条件写的有些问题，所以调试了很久，so sad。