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

归并排序

归并排序进行merge时，左右两个区间均是有序的，当选择右边区间元素时，左边区间的每个元素都比当前选择元素大，即有mid - i + 1个逆序对。所以我们可以在归并排序的过程中顺便求出逆序对。

C++代码：

class Solution {
private:
    int cnt;
    vector<int> a, b;
public:
    int InversePairs(vector<int> data) {
        a = b = data;
        cnt = 0;
        mergeSort(0, a.size() - 1);
        return cnt;
    }
    void mergeSort(int l, int r) {
        if (l >= r) return;
        
        int mid = (l + r) / 2, i = l, j = mid + 1;
        mergeSort(l, mid);
        mergeSort(mid + 1, r);
        
        for (int k = l; k <= r; k++) {
            if (j > r || (i <= mid && a[i] < a[j])) {
                b[k] = a[i++];
            } else {
                b[k] = a[j++];
                cnt += mid - i + 1;
                cnt %= 1000000007;
            }
        }
        
        for (int k = l; k <= r; k++) {
            a[k] = b[k];
        }
    }
};

时间复杂度：O(NlogN)

空间复杂度：O(N)