LeetCode/数组中的逆序对

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

最简单的思路就是二重循环暴力匹配
更优的方法是通过归并递归，先拆分成子问题，先计算区间内的逆序数，然后归并，同时计算区间之间的逆序数，并把总数加起来
计算两区间之间的逆序对时，可以跟合并区间操作统一起来，在归并合并区间时，我们使用了两个指针记录两区间初始位置
相互比较大小，复制给辅助数组，并轮流前进，以从前往后的方向为例，当右指针指向数小于左指针，那么它也必然小于左指针之后的数
直接计算得到了这个数相对左区间的逆序对，这是就利用了归并区间内有序的性质和区间相对位置确定的性质

class Solution {
public:
    int reversePairs(vector& nums) {
        vector tmp(nums.size());
        return mergeSort(0, nums.size() - 1, nums, tmp);//归并排序
    }
private:
    int mergeSort(int l, int r, vector& nums, vector& tmp) {
        // 终止条件
        if (l >= r) return 0;//逆序数返回0
        // 递归划分
        int m = (l + r) / 2;
        int res = mergeSort(l, m, nums, tmp) + mergeSort(m + 1, r, nums, tmp);//计算各自区间内的逆序对并排序
        // 合并阶段，计算两区间之间的逆序对
        int i = l, j = m + 1;//记录左右区间首指针
        for (int k = l; k <= r; k++)//将已排序两区间元素复制过来
            tmp[k] = nums[k];
        for (int k = l; k <= r; k++) {//排序合并
            if (i == m + 1)//左指针超出范围
                nums[k] = tmp[j++];//将右区间剩余元素补充上去
            else if (j == r + 1 || tmp[i] <= tmp[j])//右指针超出范围或者左侧元素更小
                nums[k] = tmp[i++];//将左区间元素补充上去
            else {//右侧元素更小，且都没超出范围，此时i~m元素都比 j 大
                nums[k] = tmp[j++];//插入右区间元素
                res += m - i + 1; // 统计逆序对
            }
        }
        return res;
    }
};