一、题目描述

  【JZ35】在数组中的两个数字，若是前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
  知识点：递归
  难度：☆☆☆☆java

二、解题思路

  假设一个数组为 {4,3,1,2}，则它的逆序对为：(4,3)、(4,1)、(4,2)、(3,1)。总共四个。web

  把 {4,3,1,2} 当作两个区间：{4,3} 和 {1,2}。若是把两个区间变为有序：{3,4} {1,2}，此时，有序的内部再也不有逆序对，而两个区间之间则可能存在逆序对。算法

  好比如今对比了 3 > 1，那么，3 后面的数字确定都是大于 1，的，因而，此时只要计算 3 到区间末尾总共多少个数字便可，此时就计算完了在 1 前面，比 1 还大的逆序对。接着同样计算 2。数组

  归并排序算法中就有把数组划分红区间的过程。参考资料：排序算法之归并排序svg

  下面的分析过程创建在你对归并排序很熟悉的前提。this

  假设如今要合并 {3,4} 和 {1,2}，两个序列的指针状况以下：

  此时，array[i] > array[j]，那么，逆序对数增长 mid - i + 1 。spa

  解释：两个序列都是有序的，3 比 1 大，那么 3 后面的数字确定都比 1 大，则此时逆序数增长包括 3 之内的后面全部数，即 三、4。.net

  等整个归并排序 merge 完毕，逆序对也统计完毕了。指针

三、解题代码

package pers.klb.jzoffer.veryhard;

/** * @program: JzOffer2021 * @description: 数组中的逆序对 * @author: Meumax * @create: 2020-08-12 17:05 **/
public class InversePairsCount {
    private long count;
    private int[] temp;

    public int InversePairs(int[] array) {
        temp = new int[array.length];
        mergeSort(array, 0, array.length - 1);
        return (int) (count % 1000000007);
    }

    private void mergeSort(int[] nums, int start, int end) {
        if (start >= end)
            return;
        int mid = start + (end - start) / 2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid + 1, end);
        merge(nums, start, mid, end);
    }

    private void merge(int[] nums, int start, int mid, int end) {
        int i = start, j = mid + 1, k = start;
        while (i <= mid || j <= end) {
            if (i > mid)
                temp[k++] = nums[j++];
            else if (j > end)
                temp[k++] = nums[i++];
            else if (nums[i] <= nums[j])
                temp[k++] = nums[i++];
            else {
                temp[k++] = nums[j++];
                this.count += mid - i + 1;  // nums[i] > nums[j]，说明 nums[i...mid] 都大于 nums[j]
            }
        }
        for (k = start; k <= end; k++)
            nums[k] = temp[k];
    }
}

  时间复杂度：O(NlogN)
  空间复杂度：O(N)code

四、解题心得

  本题确实属于难度较高，很难想出来的解法。通常的解法就是遍历 array，对于遍历到的 array[i]，统计 [0, i-1] 当中比它大的数字个数。这种作法的时间复杂度极其的高。

  归并排序涉及到对 array 进行分组，而后 merge。能够把这个方法背下来。