code4offer-51 数组中的逆序对

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

Description

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

示例 1:

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

限制：

0 <= 数组长度 <= 50000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Analyse

回溯法（超时）

生成所有的长度为2的子序列，再计算其中逆序对的数量

class Solution {
    // 找出所有长度为2的子序列，找出其中的逆序对
    public int reversePairs(int[] nums) {
        if (nums.length <= 1) return 0;

        helper(nums, new ArrayList<Integer>(), 0, 0);

        return count;
    }
    private int count = 0;

    private void helper(int[] nums, List<Integer> cur, int len, int startPos) {
        // base case
        if (len == 2) {
            if (cur.get(0) > cur.get(1)) { // 判断是否逆序
                count++;
            }
            return;
        }

        if (startPos >= nums.length) return;

        // recursive case
        for (int i = startPos; i < nums.length; i++) {
            // choose it
            cur.add(nums[i]);

            // explore
            helper(nums, cur, len + 1, i + 1);

            // unchoose it
            cur.remove(cur.size() - 1);
        }
    }
}

归并排序1（超时）

在归并排序的合并阶段计算逆序数

178 456
7比4大，是逆序对，7后面的所有元素（8）也和4是逆序对

class Solution {
    // 找出所有长度为2的子序列
    // 找出其中的逆序对
    public int reversePairs(int[] nums) {
        int len = nums.length;
        if (nums.length <= 1) return 0;

        mergeSort(nums, 0, len - 1);

        return count;
    }
    private int count = 0;

    private void mergeSort(int[] nums, int low, int high) {
        if (low >= high) return;

        int mid = low + (high - low) / 2;
        mergeSort(nums, 0, mid);
        mergeSort(nums, mid + 1, high);

        merge(nums, low, mid, high);
    }

    private void merge(int[] nums, int low, int mid, int high) {
        int p = low, q = mid + 1;
        int[] tmpNums = new int[high - low + 1];
        int index = 0;
        while (p <= mid && q <= high) {
            if (nums[p] > nums[q]) { // 逆序
                count += (mid - p + 1);
                tmpNums[index++] = nums[q++];
            } else {
                tmpNums[index++] = nums[p++];
            }
        }

        while (p <= mid) {
            tmpNums[index++] = nums[p++];
        }

        while (q <= high) {
            tmpNums[index++] = nums[q++];
        }

        System.arraycopy(tmpNums, 0, nums, low, high - low + 1);
    }
}

归并排序2（通过）

同样是归并排序，这个为什么可以通过而上一个不行？

class Solution {
    // 找出所有长度为2的子序列
    // 找出其中的逆序对
    public int reversePairs(int[] nums) {
        int len = nums.length;
        if (nums.length <= 1) return 0;
        int[] tempNums = new int[len];

        System.arraycopy(nums, 0, tempNums, 0, len);

        return mergeSort(nums, 0, len - 1, tempNums);
    }

    private int mergeSort(int[] nums, int low, int high, int[] temp) {
        if (low >= high) return 0;

        int mid = low + (high - low) / 2;
        int left = mergeSort(nums, low, mid, temp);
        int right = mergeSort(nums, mid + 1, high, temp);

        if (nums[mid] <= nums[mid + 1]) {
            return left + right;
        }

        int cross = merge(nums, low, mid, high, temp);

        return left + right + cross;
    }

    // 双指针法，将nums[low:mid] 通过 tmpNums临时空间 合并
    private int merge(int[] nums, int low, int mid, int high, int[] tmpNums) {
        System.arraycopy(nums, low, tmpNums, low, high - low + 1);

        int p = low, q = mid + 1;

        int count = 0;
        int index = low;
        while (p <= mid && q <= high) {
            if (tmpNums[p] > tmpNums[q]) {
                count += (mid - p + 1);
                nums[index++] = tmpNums[q++];
            } else {
                nums[index++] = tmpNums[p++];
            }
        }

        while (p <= mid) {
            nums[index++] = tmpNums[p++];
        }

        while (q <= high) {
            nums[index++] = tmpNums[q++];
        }

        return count;
    }
}