劍指Offer_35_數組中的逆序對

題目描述

在數組中的兩個數字，如果前面一個數字大于後面的數字，則這兩個數字組成一個逆序對。輸入一個數組,求出這個數組中的逆序對的總數P。并将P對1000000007取模的結果輸出。 即輸出P%1000000007 

輸入描述:

題目保證輸入的數組中沒有的相同的數字

資料範圍：

    對于%50的資料,size<=10^4

    對于%75的資料,size<=10^5

    對于%100的資料,size<=2*10^5

      

輸入例子:

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

輸出例子:

7      

解題思路

利用歸并排序的思想，每次排序相鄰兩段的資料并統計逆序，相對于前後的資料段之間沒有相對資料沒有改變。

實作

public class Solution {
    public int InversePairs(int [] array) {
        if(array == null || array.length <= ) return ;
        int[] copy = new int[array.length];
        for (int i =; i < array.length; i++){
            copy[i] = array[i];
        }
        return mergerCount(array, copy, , array.length-);
    }

    private int mergerCount(int[] array, int[] copy, int start, int end) {
        if (start >= end){
            if (start == end) copy[start] = array[start];
            return ;
        }

        int mid = (start + end) / ;

        int c1 = mergerCount(copy, array, start, mid);
        int c2 = mergerCount(copy, array, mid + , end);

        int count = ;

        int l = mid;
        int r = end;
        int index = end;

        while (r > mid && l >= start){
            if (array[r] >= array[l]){
                copy[index--] = array[r--];
            }else {
                //前面的目前值大于後面的目前值，那麼前面的目前值大于後面剩餘部分，都是逆序對
                count += r - mid;
                copy[index--] = array[l--];
                if (count >= ) count %= ;
            }
        }
        while (r > mid) copy[index--] = array[r--];
        while (l >= start) copy[index--] = array[l--];

        return (count + c1 + c2) % ;
    }
}