原题链接

<br//>

描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

对于50%50%的数据,size\leq 10^4siz**e≤104
对于100%100%的数据,size\leq 10^5siz**e≤105

示例

输入：[1,2,3,4,5,6,7,0]
返回值：7

思路

归并排序。排序的时候操作的是两个子数组a，b，遍历两个数组如果发现 a 当前的数大于 b 当前的数，那么说明a 中该数后面的数都大于 b 中的那个数，以此统计逆序对数。

解答

package com.klaus.sort;

import org.junit.Test;

public class MergeSort {
    int cnt = 0;

    public void merge(int[] a, int low, int high) {
        if (low < high) {
            // int mid = low + (high - low) / 2;
            int mid = (low + high) / 2;
            merge(a, low, mid);
            merge(a, mid + 1, high);
            sort(a, low, high, mid);
        }
    }

    public void sort(int[] a, int low, int high, int mid) {
        int i = low, j = mid + 1;
        int[] tmp = new int[high - low + 1];
        int p = 0;

        // 两边相互比较
        while (i <= mid && j <= high) {
            if (a[i] <= a[j]) {
                tmp[p++] = a[i++];
            } else {
                tmp[p++] = a[j++];
                cnt += (mid - i + 1);//就这个！！！
            }
        }

        // 把还没比较完的直接放入tmp
        while (i <= mid) {
            tmp[p++] = a[i++];
        }
        while (j <= high) {
            tmp[p++] = a[j++];
        }
        p = 0;
        // 这是为什么要保存刚刚的 low、high
        for (int t = low; t <= high; t++) {
            a[t] = tmp[p++];
        }
    }

}

JZ35 数组中的逆序对