题解 | #数组中的逆序对#

1. 这个题的要用归并排序做，否则时间复杂度太大。
2. 原理，当左边的一个数比右边的一个数大的时候，那么包括左边的左边所有的数都比该数大，从而算出逆序对的个数。
3. 然后从大的方面递归就相当于算出了最终完整的答案。
   

class Solution {
public:
    int count = 0;
    int InversePairs(vector<int> data) {
        if(data.size()<2) return 0;
        // 长度小于2则无逆序对

        mergeSort(data,0,data.size()-1);

        return count;

    }

    void mergeSort(vector<int>& data, int left, int right){

        int mid = (left+right)/2;

        if(left<right){
            //
            mergeSort(data,left,mid);
            mergeSort(data,mid+1,right);

            merge(data,left,mid,right);

        }
    }


    void merge(vector<int>& data, int left,int mid, int right){

        vector<int> arr(right - left+1,0);
        int i = left, j = mid+1, k = 0, origin = left;


        while(i<=mid&&j<=right){
            if(data[i]<=data[j]){
                arr[k++] = data[i++];
            }else{
                arr[k] = data[j];

                count += mid+1-i;
                count %= 1000000007;

                k++;
                j++;

            }
        }

        // 左子数组还有元素时，全部放入临时数组
        for(;i<=mid;){
            arr[k++] = data[i++];
        }
        // 右子数组还有元素时，全部放入临时数组
         for(;j<=right;){
            arr[k++] = data[j++];
        }
        // 将临时数组中的元素放入到原数组的指定位置
        for(int num:arr){
            data[origin++] = num;
        }

    }
};