51.数组中的逆序对

raylan.chen大约 1 分钟

class Solution {
    int[] record, tmp;
    public int reversePairs(int[] record) {
        this.record = record;
        tmp = new int[record.length];
        return mergeSort(0, record.length - 1);
    }
    private int mergeSort(int l, int r) {
        // 终止条件
        if (l >= r) return 0;
        // 递归划分
        int m = (l + r) / 2;
        int res = mergeSort(l, m) + mergeSort(m + 1, r);
        // 合并阶段
        int i = l, j = m + 1;
        for (int k = l; k <= r; k++)
            tmp[k] = record[k];
        for (int k = l; k <= r; k++) {
            if (i == m + 1)
                record[k] = tmp[j++];
            else if (j == r + 1 || tmp[i] <= tmp[j])
                record[k] = tmp[i++];
            else {
                record[k] = tmp[j++];
                res += m - i + 1; // 统计逆序对
            }
        }
        return res;
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solutions/622496/jian-zhi-offer-51-shu-zu-zhong-de-ni-xu-pvn2h/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

在归并排序的合并阶段统计「逆序对」的数量，

在排序的过程中，采用 tmp 数组临时存储已排好序的左右子数组，随后利用 tmp 数组来比较并更换 record 原数组的元素顺序

另外，res 不可设置为全局变量，否则可能遇到左子数组 $res_{left} = 1$，右子数组原本为 $res_{right} = 1$ ，却与左子数组的结果叠加 $res = res_{left} + res_{right}$ ，随后返回调用函数时又进行了一次叠加 int res = mergeSort(l, m) + mergeSort(m + 1, r);

51.数组中的逆序对

51.数组中的逆序对

参考链接

优秀题解