数组中的逆序对

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数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

思路：归并排序。每次数据分成2两份，后对两组数据进行排序。使用两个指针指向数组末尾，当前方的数据大于后方的数据时，逆序对的个数为后一个数组中从0开始到指针对应位置的个数。

class Solution {
public:
    int InversePairs(vector<int> data) {
        long result = 0;
        int length = data.size();
        mergeSort(data,result);
        return result % 1000000007;
    }
    //归并排序
    
    //一个元素时需要原样返回，所以这里使用引用。
    void mergeSort(vector<int> &data,long &result) {
        if (data.size() < 2) {
            return;
        }
        int mid = data.size() / 2;
        //创建两个数组，用来存放临时数据   
        vector<int>left(mid);
        vector<int>right(data.size()-mid);
        //将数据放进两个数组中
        for (int  i = 0; i <mid; i++)
        {
            left[i] = data[i];
        }
        for (int j = mid; j <data.size(); j++)
        {
            right[j - mid] = data[j];
        }
        mergeSort(left,result);
        mergeSort(right,result);

        //合并
        //merge                     
        merge(data,left,right,result);
    }
    //原始的vector数据，需要更新数据所以需要引用。vector左边数据，右边右侧数据
    void merge(vector<int>&result,vector<int>left,vector<int>right,long &total) {
        //如果右侧左侧末尾数据大于右侧默认数据，则左侧数据增加数字为右侧数据个数只和
        int i=left.size()-1, j=right.size()-1, k=result.size()-1;
        
        while (i>=0&&j>=0)
        {
            //左侧末尾小于右侧末尾
            if (left[i] < right[j]) {
                result[k--] = right[j--];
        
            }//左侧末尾数字大于右侧末尾数字    if (left[i] > right[j]) 
            else{
                //因为j=0时前面有1个数字，所以这里需要j+1
                total +=(j+1);
                result[k--] = left[i--];
            }
        }
        //其中一个集合中数据为空

        while (i>=0)
        {
            result[k--] = left[i--];
        }
        while (j>=0)
        {
            result[k--] = right[j--];
        }
    }
};