【剑指offer刷题】--数组中的逆序对

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

归并排序的改进，把数据分成前后两个数组(递归分到每个数组仅有一个数据项)，

合并数组，合并时，出现前面的数组值array[i]大于后面数组值array[j]时；则前面

数组array[i]~array[mid]都是大于array[j]的，count += end-j+1

参考剑指Offer，但是感觉剑指Offer归并过程少了一步拷贝过程。

还有就是测试用例输出结果比较大，对每次返回的count mod(1000000007)求余

先把数组分割成子数组，先统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需要对数组进行排序。如果对排序算法很熟悉，我们不难发现这个过程实际上就是归并排序。参考代码如下：

class Solution {
public:
long countRes=0 ;
    int InversePairs(vector<int> data) {
        //countRes = 0;
        if(data.size() <=1)
            return 0;
        MergeSort(data,0,data.size()-1);
        return countRes%1000000007 ;
    }
     
    void MergeSort(vector<int>& data,int first,int end){
        if(first < end){
            int mid = (first + end)/2;
            MergeSort(data,first,mid);
            MergeSort(data,mid+1,end);
            vector<int> tmp;
            MergeArray(data,first,mid,end,tmp);
        }
    }
    void MergeArray(vector<int>& data,int first,int mid,int end,vector<int> &tmp){
        int i = first;//int m = mid;
        int j = mid + 1;//int n = end;
     
        while(i<=mid && j<=end){
            if(data[i] > data[j]){
                tmp.push_back(data[i++]);
                countRes += end - j+1;//更新逆序对数
            }
            else{
                tmp.push_back(data[j++]);
            }
        }
        while(i<=mid)
            tmp.push_back(data[i++]);
        while (j<=end)
            tmp.push_back(data[j++]);
 
        //更新data数组
        int k = 0;
        for (int i = first; i <= end &&k<tmp.size(); i++)
            data[i] = tmp[k++];
         
    }
};