算法:数组中的逆序对

数组中的逆序对

数组中的逆序对

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

即输出P%1000000007

输入描述:

题目保证输入的数组中没有的相同的数字数据范围:

对于%50的数据,size<=10^4

对于%75的数据,size<=10^5

对于%100的数据,size<=2x10^5

输入

1,2,3,4,5,6,7,0

输出

7

分析

本质上逆序就是在归并排序的归并过程中产生的数字位置提升的总和数

所以求数组中的逆序数, 只要对数组进行归并排序即可!

代码

public class Solution {
    private int res;

    public int InversePairs(int[] array) {
        res = 0;
        if (array != null && array.length > 0) {
            divide(array, 0, array.length - 1);
        }
        return res;
    }

    // 数组切分过程
    private void divide(int[] arr, int start, int end) {
        if (start >= end) return;

        int mid = (end - start) / 2 + start;
        divide(arr, start, mid);
        divide(arr, mid + 1, end);

        merge(arr, start, mid, end);
    }

    // 数组归并过程
    private void merge(int[] arr, int start, int mid, int end) {
        int[] table = new int[end - start + 1];

        int i = start, j = mid + 1, k = 0;
        while (i <= mid && j <= end) {
            if (arr[i] <= arr[j]) table[k++] = arr[i++];
                // 产生了逆序
            else {
                table[k++] = arr[j++];
                // 从a[i]开始到a[mid]必定都是大于这个a[j]的
                // 因为此时分治的两边已经是各自有序了
                res = (res + mid - i + 1) % 1000000007;
            }
        }

        while (i <= mid) table[k++] = arr[i++];
        while (j <= end) table[k++] = arr[j++];

        // 覆盖数组
        for (k = 0; k < table.length; ++k) {
            arr[start + k] = table[k];
        }
    }
}