1.数组中的逆序对
思路:先把数组分隔成子数组,统计出子数组内部的逆序对的数目,然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中,还需对数组进行排序。实际就是归并排序的思想。例如7564,我们先将其分为,75,64,再分解为7,5,6,4,然后把长度为1的子数组合并、排序并统计逆序对,得到57,46,再把长度为2的子数组合并、排序并统计逆序对得到4567.
class Solution { public: int InversePairs(vector<int> data) { int length=data.size(); if(length<=0) return 0; vector<int> copy; for(int i=0;i<length;i++) copy.push_back(data[i]); long long count=InversePairsCore(data,copy,0,length-1); return count%1000000007; } long long InversePairsCore(vector<int> &data,vector<int> ©,int start,int end) { if(start==end) { copy[start]=data[start]; return 0; } int length=(end-start)/2; long long left=InversePairsCore(copy,data,start,start+length); long long right=InversePairsCore(copy,data,start+length+1,end); int i=start+length; int j=end; int indexcopy=end; long long count=0; while(i>=start&&j>=start+length+1) { if(data[i]>data[j]) { copy[indexcopy--]=data[i--]; count=count+j-start-length; //count=count+j-(start+length+1)+1; } else { copy[indexcopy--]=data[j--]; } } for(;i>=start;i--) copy[indexcopy--]=data[i]; for(;j>=start+length+1;j--) copy[indexcopy--]=data[j]; return left+right+count; } };