剑指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

思路

剑指offer书里的思路，归并排序思想
分组找逆序对，合并再找
比如  7 5 6 4 分成7 5一组、6 4一组，第一组逆序对1个，第二组逆序对1个，排序成5 7和4  6然后合并看有几个逆序，
设置两个指针i,j分别指向两组的最后一个结点，然后比较，,7>6，所以逆序对+1，i指针前移一位，5<6，逆序对不变
j指针前移一位5>4，逆序对+1,i指针前移一位，比较的时候每次都把大的数字加到copy数组里（copy数组是当前两组合并的结果，排完序的），一组已经没数字了，把另外一组的一次加进copy

code

class Solution {
public:

    int InversePairCore(vector<int>& data,int*& copy,int start,int end){
        //划分成单个的时候要给copy赋值
        if(start==end){
            copy[start]=data[start];
            return 0;
        }
        int length=(end-start)/2;
        //得到第一组的逆序对
        int left=InversePairCore(data,copy,start,start+length)%1000000007;
        //得到第二组的逆序对
        int right=InversePairCore(data,copy,start+length+1,end)%1000000007;
        //i，j分别为两组最后一个元素下标
        int i=start+length;
        int j=end;
        int indexCopy=end;
        int count=0;
        while(i>=start&&j>=start+length+1){
            //第一组里的数字比第二组的大，逆序对+1
            第一组里的数字比第二组的小，逆序对不变
            if(data[i]>data[j]){
                copy[indexCopy--]=data[i--];
                count=(count+j-start-length)%1000000007;
            }else{
                copy[indexCopy--]=data[j--];
            }
        }
        //把剩余的元素加进copy数组里去
        for(;i>=start;--i)
            copy[indexCopy--]=data[i];
        for(;j>=start+length+1;--j)
            copy[indexCopy--]=data[j];
        //copy是排好序的，赋值给data
        for(unsigned int i=start;i<=end;++i)
            data[i]=copy[i];
        return (left+right+count)%1000000007;
    }

    int InversePairs(vector<int> data) {
        int length=data.size();
        if(length<=1)
            return 0;
        int *copy=new int[length];
        for(unsigned int i=0;i<length;++i)
            copy[i]=0;
        int count=InversePairCore(data,copy,0,length-1);
        delete []copy;
        return count;
    }
};