[数据结构与算法]leetcode:剑指51 逆序对 （归并排序）

思路：

1.使用copy和tmp来复制和记录
2.left right和mid分成【left， mid】和【mid + 1， right】继续分治，然后mergeandcount记录两个相邻有序子列的逆序对
3.mergeandcount两个相邻有序列合并，k个位置双指针i和j依次往后，统计后面列形成的逆序对为mid + 1 - i
4.剪枝，若两个子列依次有序就不用mergeandcount

ac代码：

class Solution {
    // java的数组是地址传递
    // 逆序数组用归并排序的思想解决
    public int reversePairs(int[] nums) {
        int n = nums.length;
        if(n < 2) return 0;
        // 来一份拷贝，保持原数组
        int[] copy = new int[n];
        for (int i = 0; i < n; i++) {
            copy[i] = nums[i];
        }

        // 来一份tmp，用于每次换的时候记录旧的
        int[] tmp = new int[n];

        // 开始找逆序对
        // 重载
        // 左右都是闭区间
        return reversePair(copy, tmp, 0, n - 1);

    }

    /**
     * [left, mid] 和 [mid + 1, right] 都是递增
     * @param nums
     * @param tmp
     * @param left
     * @param right
     * @return
     */
    private int reversePair(int[] nums, int[] tmp, int left, int right) {
        // 如果只有一个
        if(left == right) return 0;
        // 取中间, 防溢出
        int mid = left + (right - left) / 2;
        int n1 = reversePair(nums, tmp, left, mid);
        int n2 = reversePair(nums, tmp, mid + 1, right);

        // 若整个已经有序, 剪枝
        if(nums[mid] <= nums[mid + 1]) return n1 + n2;
        // 两个之间的逆序对
        int crosscount = mergeAndCount(nums, tmp, left, right);
        return n1 + n2 + crosscount;
    }

    private int mergeAndCount(int[] nums, int[] tmp, int left, int right) {
        int count = 0;
        // i是左半子列，j是右半子列开始
        int mid = left + (right - left) / 2;
        int i = left, j = mid + 1;
        // nums改变， tmp记录原来的
        for (int k = left; k <= right; k++) {
            tmp[k] = nums[k];
        }
        // 开始双指针归并 + 统计逆序
        for (int k = left; k <= right; k++) {
            // 左子列用尽
            if(i == mid + 1) {
                nums[k] = tmp[j++];
            }
            // 右子列用尽
            else if(j == right + 1) {
                nums[k] = tmp[i++];
            }
            else if(tmp[i] <= tmp[j]) {
                nums[k] = tmp[i++];
            }
            else if(tmp[i] > tmp[j]) {
                nums[k] = tmp[j++];
                // 核心计算逆序对
                // 两个子列之间出现的逆序对
                count += (mid + 1 - i);
            }
        }
        return count;
    }
}

归并排序带出来 + 逆序对：

public class Offer51 {
    // java的数组是地址传递
    // 逆序数组用归并排序的思想解决
    public int reversePairs(int[] nums, int[] copy) {
        int n = nums.length;
        if(n < 2) return 0;
        // 来一份拷贝，保持原数组

        for (int i = 0; i < n; i++) {
            copy[i] = nums[i];
        }

        // 来一份tmp，用于每次换的时候记录旧的
        int[] tmp = new int[n];

        // 开始找逆序对
        // 重载
        // 左右都是闭区间
        return reversePair(copy, tmp, 0, n - 1);

    }

    /**
     * [left, mid] 和 [mid + 1, right] 都是递增
     * @param nums
     * @param tmp
     * @param left
     * @param right
     * @return
     */
    private int reversePair(int[] nums, int[] tmp, int left, int right) {
        // 如果只有一个
        if(left == right) return 0;
        // 取中间, 防溢出
        int mid = left + (right - left) / 2;
        int n1 = reversePair(nums, tmp, left, mid);
        int n2 = reversePair(nums, tmp, mid + 1, right);

        // 若整个已经有序, 剪枝
        if(nums[mid] <= nums[mid + 1]) return n1 + n2;
        // 两个之间的逆序对
        int crosscount = mergeAndCount(nums, tmp, left, right);
        return n1 + n2 + crosscount;
    }

    private int mergeAndCount(int[] nums, int[] tmp, int left, int right) {
        int count = 0;
        // i是左半子列，j是右半子列开始
        int mid = left + (right - left) / 2;
        int i = left, j = mid + 1;
        // nums改变， tmp记录原来的
        for (int k = left; k <= right; k++) {
            tmp[k] = nums[k];
        }
        // 开始双指针归并 + 统计逆序
        for (int k = left; k <= right; k++) {
            // 左子列用尽
            if(i == mid + 1) {
                nums[k] = tmp[j++];
            }
            // 右子列用尽
            else if(j == right + 1) {
                nums[k] = tmp[i++];
            }
            else if(tmp[i] <= tmp[j]) {
                nums[k] = tmp[i++];
            }
            else if(tmp[i] > tmp[j]) {
                nums[k] = tmp[j++];
                // 核心计算逆序对
                // 两个子列之间出现的逆序对
                count += (mid + 1 - i);
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] a = {7, 5, 6, 4};
        int[] copy = new int[4];
        // 寄生兽，还是要调用类
        Offer51 obj = new Offer51();
        System.out.println(obj.reversePairs(a, copy));
        for (int i = 0; i < 4; i++) {
            if(i == 0) System.out.printf("%d", copy[i]);
            else System.out.printf(" %d", copy[i]);
        }

    }
}

总结：
复习了归并排序 和 逆序对