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

1. 首先是归并。然后归并的时候进行比较

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;
        }

    }
};