逆序对

在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。给你一个数组，求出这个数组中逆序对的总数。
概括：如果a[i] > a[j] 且 i < j， a[i] 和 a[j] 构成一个逆序对。

您在真实的面试中是否遇到过这个题？ Yes
样例
序列 [2, 4, 1, 3, 5] 中，有 3 个逆序对 (2, 1), (4, 1), (4, 3)，则返回 3 。

思路
在归并排序的merge过程中计算逆序对数目

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];
        }
    }
};