51-数组中的逆序对

剑指 Offer 51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

method: 归并排序

int mergeSort(vector<int>& nums, int l, int r, vector<int>& tmp) {
    if (l == r) return 0;
    int mid = l + (r - l) / 2;
    int leftNum = mergeSort(nums, l, mid, tmp);
    int rightNum = mergeSort(nums, mid + 1, r, tmp);
    int curNum = 0;
    int cnt = l, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (nums[i] <= nums[j]) {
            tmp[cnt++] = nums[i++];
        } else {
            tmp[cnt++] = nums[j++];
            curNum += (mid - i + 1);    // [i, mid]都是大于nums[j]的
        }
    }
    while (i <= mid) tmp[cnt++] = nums[i++];
    while (j <= r) tmp[cnt++] = nums[j++];
    for (int k = l; k <= r; k++) {
        nums[k] = tmp[k];
    }
    return curNum + leftNum + rightNum;
}
int reversePairs(vector<int>& nums) {
    int n = nums.size();
    if (n < 2) return 0;
    vector<int> tmp(n);
    return mergeSort(nums, 0, n - 1, tmp);
}