题目描述

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

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

0 <= 数组长度 <= 50000

测试用例

• 功能测试（输入未经排序的数组、递增排序的数组、递减排序的数组；输入的数组中包含重复的数字）
• 边界值测试（输入的数组中只有两个数字；输入的数组只有一个数字）
• 特殊输入测试（表示数组的指针为空指针）

题目考点

• 考察应聘者分析复杂问题的能力。
• 考察应聘者对归并排序的掌握程度。

解题思路

利用归并排序实现时间复杂度为O(nlogn)

如数组{7, 5, 6, 4}中

1. 把长度为4的数组分解成两个长度为2的子数组；
2. 把长度为2的数组分解成两个成都为1的子数组；
3. 把长度为1的子数组合并、排序并统计逆序对，得到(7, 5)、(6, 4)；
4. 把长度为2的子数组合并、排序并统计逆序对，得到(7, 6)、(7, 4)、(5, 4)；

参考解题

public class 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] 计算逆序对个数并且排序
     *
     * @param nums
     * @param left
     * @param right
     * @param temp
     * @return
     */
    private int reversePairs(int[] nums, int left, int right, int[] temp) {
        if (left == right) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        int leftPairs = reversePairs(nums, left, mid, temp);
        int rightPairs = reversePairs(nums, mid + 1, right, temp);

        // 如果整个数组已经有序，则无需合并，注意这里使用小于等于
        if (nums[mid] <= nums[mid + 1]) {
            return leftPairs + rightPairs;
        }

        int crossPairs = mergeAndCount(nums, left, mid, right, temp);
        return leftPairs + rightPairs + crossPairs;
    }

    /**
     * nums[left..mid] 有序，nums[mid + 1..right] 有序
     *
     * @param nums
     * @param left
     * @param mid
     * @param right
     * @param temp
     * @return
     */
    private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }

        int i = left;
        int j = mid + 1;

        int count = 0;
        for (int k = left; k <= right; k++) {
            // 有下标访问，得先判断是否越界
            if (i == mid + 1) {
                nums[k] = temp[j];
                j++;
            } else if (j == right + 1) {
                nums[k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {
                // 注意：这里是 <= ，写成 < 就不对，请思考原因
                nums[k] = temp[i];
                i++;
            } else {
                nums[k] = temp[j];
                j++;
                
                // 在 j 指向的元素归并回去的时候，计算逆序对的个数，只多了这一行代码
                count += (mid - i + 1);
            }
        }
        return count;
    }
}

补充

归并排序代码如下：

/**
 * 归并排序
 */
public class MergeSort {
    /**
     * 归并排序
     * @param array
     * @param low
     * @param high
     * @return
     */
    public int[] mergeSort(int[] array, int low, int high) {
        if (low < high) {
            int mid = (low + high) >> 1;
            // 辅助数组
            int[] temp = new int[array.length];
            mergeSort(array, low, mid);
            mergeSort(array, mid + 1, high);
            merge(array, temp, low, mid, high);
        }
        return array;
    }

    /**
     * 归并
     * @param array
     * @param temp
     * @param low
     * @param mid
     * @param high
     */
    public void merge(int[] array, int[] temp, int low, int mid, int high) {

        // 代表左边下标
        int i = low;
        // 代表右边下标
        int j = mid + 1;
        // 代表辅助数组的下标
        int k = 0;
        while (i <= mid && j <= high) {
            if (array[i] < array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }
        // 如果左边有剩余元素，移入辅助数组
        while (i <= mid) {
            temp[k++] = array[i++];
        }
        // 如果右边有剩余元素，移入辅助数组
        while (j <= high) {
            temp[k++] = array[j++];
        }
        // 临时数组覆盖原数组
        System.arraycopy(temp, 0, array, low, high - low + 1);

    }
}