劍指offer——數組中的逆序數對

題目描述：

在數組中的兩個數字，如果前面一個數字大于後面的數字，則這兩個數字組成一個逆序對。輸入一個數組,求出這個數組中的逆序對的總數P。并将P對1000000007取模的結果輸出。 即輸出P%1000000007

輸入描述:

題目保證輸入的數組中沒有的相同的數字

資料範圍：

對于%50的資料,size<=10^4

對于%75的資料,size<=10^5

對于%100的資料,size<=2*10^5      

示例1

輸入

1,2,3,4,5,6,7,0

輸出

7

class Solution {
public:
    int InversePairs(vector<int> data) {
        if(data.size()<2)
            return 0;
        int p=0;
        for(int i=0;i<data.size();i++){
            for(int j=i+1;j<data.size();j++){
                if(data[i]>data[j])
                    p++;
            }
        }
        return p%1000000007;
    }
};      

class Solution {
public:
    int InversePairs(vector<int> data) {
        if(data.size()<2)
            return 0;
        int length=data.size();
        vector<int> copy(length);
        for(int i=0;i<length;i++){
            copy[i]=data[i];
        }
        long long count=InverseCore(data,copy,0,length-1);
        return count%1000000007;
    }
    //data是子數組有序，copy是合并後有序數組
    long long InverseCore(vector<int>& data,vector<int>& copy,int start,int end){
        if(start==end){
            copy[start]=data[start];
            return 0;
        }
        int length=(end-start)>>1;
        long long left=InverseCore(copy,data,start,start+length);
        long long right=InverseCore(copy,data,start+length+1,end);
        int i=start+length;
        int j=end;
        int copyindex=end;
        long long count=0;
        while(i>=start&&j>=start+length+1){
            if(data[i]>data[j]){
                copy[copyindex--]=data[i--];
                count+=j-start-length;
            }else{
                copy[copyindex--]=data[j--];
            }
        }
        while(i>=start){
            copy[copyindex--]=data[i--];
        }
        while(j>=start+length+1){
            copy[copyindex--]=data[j--];
        }
        return left+right+count;
    }
};