逆序对

2020-05-02

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

链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof

示例 1:

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

解题思路

在归并数组时，加上统计逆序对的逻辑。

当 $rightArray$ 中的数据小于 $leftArray$ 时，可与 $leftArray$ 中的数据构成逆序对,计数器更新

图片来自于：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/bao-li-jie-fa-fen-zhi-si-xiang-shu-zhuang-shu-zu-b/

详情可参考视频链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/shu-zu-zhong-de-ni-xu-dui-by-leetcode-solution/

public class MergeSort {
    /*
    数组中的逆序对
    链接: https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/shu-zu-zhong-de-ni-xu-dui-by-leetcode-solution/
    逆序对计数的过程发生在 归并排序的合并数组过程中
    */
    public int reversePairs(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return 0;
        }
        int[] copy = new int[len];
        for (int i = 0;i < len;i++) {
            copy[i] = nums[i];
        }
        int[] temp = new int[len];
        return reversePairs(copy, 0, len - 1, temp);
    }
    /*
     * nums[left...right] 计算逆序对个数并排序
     */
    private int reversePairs(int[] copy, int left, int right, int[] temp) {
        if (left == right) {
            return 0;
        }
        int mid = left + (right - left) / 2; // 当left和right很大的时候 (left+right)/2 会溢出
        int leftCounts = reversePairs(copy, left, mid, temp);
        int rightCounts = reversePairs(copy, mid + 1, right, temp);
        // 当数组已经有序的时候
        if (copy[mid] <= copy[mid+1]) return leftCounts+rightCounts;
        int crossCounts = mergeAndCount(copy, left, mid, right, temp);
        return leftCounts + rightCounts + crossCounts;
    }
    private int mergeAndCount(int[] copy, int left, int mid, int right, int[] temp) {
        for (int i = left;i <= right;i++) {
            temp[i] = copy[i];
        }
        // 两个子区间的第一个下标
        int i = left;
        int j = mid + 1;
        int count = 0; // 计数器
        // 遍历辅助数组
        for (int k = left;k <= right;k++) {
            if (i == mid + 1) {
                // 如果左边数组用完
                copy[k] = temp[j];
                j++;
            } else if (j == right + 1) {
                copy[k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {
                // 归并小的数据
                copy[k] = temp[i];
                i++;
            } else {
                copy[k] = temp[j];
                j++;
                count += (mid - i + 1);
            }
        }
        return count;
    }
}