剑指35-数组中的逆序对

归并排序、数组

解法1

暴力（超时）

class Solution {
public:
    int InversePairs(vector<int> data) {
        int res=0;
        for(int i=data.size();i>=1;i--)
        {
            for(int j=i-1;j>=0;i--)
            {
                if(data[i]<data[j]) res++;
            }
        }
        return res;
    }
};

解法2：归并排序

根据归并排序的特点，每次对比两个有序数组，符合条件的逆序对数+1，整体的算法其实就是一个归并排序，这里我把划分和归并合并成了一个方法，难点或者说巧妙的点在于res+=middle-l+1，因为序列有序，所以当遇到data[l]>=data[r]的时候，所以l右边的数都符合条件

class Solution {
public:
    int InversePairs(vector<int> data) {
        mergeSort(data, 0, data.size()-1);
        return res;
    }

    void mergeSort(vector<int> &data, int start, int end)
    {
        if (start >= end) return;
        int n = end - start + 1;
        int middle = start + (end - start) /2;

        mergeSort(data, start, middle); //递归
        mergeSort(data, middle + 1, end);

        vector<int> newList(n); //开辟新空间
        int pivot =0, l=start, r=middle+1;
        while (l <= middle && r <= end)
        {
            if(data[l] >= data[r])
            {
                newList[pivot++]=data[r++];
                res+=middle-l+1;
                res=res%1000000007;
            }
            else
            {
                newList[pivot++]=data[l++];
            }
        }
        while (l <= middle) //加上剩余的值
        {
            newList[pivot++] = data[l++];
        }
        while (r <= end)
        {
            newList[pivot++] = data[r++];
        }
        for (int i = 0; i < n; i++) //修改原数组的值
        {
            data[start++] = newList[i];
        }
    }
private:
    int res=0;
};

参考链接：https://www.nowcoder.com/questionTerminal/96bd6684e04a44eb80e6a68efc0ec6c5?answerType=1&f=discussion