在數(shù)組中的兩個數(shù)字如果前面一個數(shù)字大于后面的數(shù)字娜搂，則這兩個數(shù)字組成一個逆序?qū)Υ侥痢＝o你一個數(shù)組风范，求出這個數(shù)組中逆序?qū)Φ目倲?shù)。
概括：如果a[i] > a[j] 且 i < j摹恰， a[i] 和 a[j] 構(gòu)成一個逆序?qū)Α?/p>
您在真實的面試中是否遇到過這個題辫继？ Yes
樣例
序列 [2, 4, 1, 3, 5] 中，有 3 個逆序?qū)?(2, 1), (4, 1), (4, 3)俗慈，則返回 3 姑宽。
思路
在歸并排序的merge過程中計算逆序?qū)?shù)目
class Solution {
public:
/**
* @param A an array
* @return total of reverse pairs
*/
long long reversePairs(vector<int>& A) {
// Write your code here
if(A.size()==0){
return 0;
}
vector<int>temp(A.size(),0);
int count = 0;
mergeSort(A,temp,0,A.size()-1,count);
return count;
}
void mergeSort(vector<int>& A,vector<int>& temp,int left,int right,int &count) {
if(left == right) {
return;
}
int mid = (left + right)/2;
mergeSort(A,temp,left,mid,count);
mergeSort(A,temp,mid+1,right,count);
merge(A,temp,left,mid,right,count);
}
void merge(vector<int>& A,vector<int>& temp,int left,int mid,int right,int & count) {
for(int i=left;i<=mid;i++) {
int leftDigit = A[i];
for(int j=right;j>=mid+1;j--){
int rightDigit = A[j];
if(leftDigit<=rightDigit) {
continue;
} else {
int bigerCount = (j-(mid+1))+1;
count += bigerCount;
break;
}
}
}
int i = left;
int j = mid+1;
int k = left;
while(i<=mid&&j<=right) {
if(A[i]<A[j]) {
temp[k++] = A[i++];
} else {
temp[k++] = A[j++];
}
}
for(int p=i;p<=mid;p++) {
temp[k++] = A[p];
}
for(int p=j;p<=right;p++){
temp[k++]=A[p];
}
for(int p=left;p<=right;p++){
A[p]=temp[p];
}
}
};
