#yyds幹貨盤點# 面試必刷TOP101：數組中的逆序對

1.簡述：

描述

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

資料範圍：  對于  的資料, 對于  的資料, 

數組中所有數字的值滿足 

要求：空間複雜度 ，時間複雜度 

輸入描述：

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

示例1

輸入：

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

傳回值：

7      

示例2

輸入：

[1,2,3]      

public class Solution {
    int count = 0;
    public int InversePairs(int [] array) {
        // 長度小于2則無逆序對
        if(array.length < 2)
            return 0;
        // 進入歸并
        mergeSort(array,0,array.length-1);
        return count;
    }

    public void mergeSort(int[] array,int left,int right){
        // 找分割點
        int mid = left+(right-left)/2;
        if(left < right){
            // 左子數組
            mergeSort(array,left,mid);
            // 右子數組
            mergeSort(array,mid+1,right);
            // 并
            merge(array,left,mid,right);
        }
    }

    public void merge(int[] array,int left,int mid,int right){
        // 建立臨時數組，長度為此時兩個子數組加起來的長度
        int[] arr =  new int[right-left+1];
        // 臨時數組的下标起點
        int c = 0;
        // 儲存在原數組的起點下标值
        int s = left;
        // 左子數組的起始指針
        int l = left;
        // 右子數組的起始指針
        int r = mid+1;
        while(l <= mid && r <= right ){
            // 當左子數組的目前元素小的時候，跳過，無逆序對
            if(array[l] <= array[r]){
                // 放入臨時數組
                arr[c] = array[l];
                // 臨時數組下标+1
                c++;
                // 左子數組指針右移
                l++;
            }else{ // 否則，此時存在逆序對
                // 放入臨時數組
                arr[c] = array[r];
                // 逆序對的個數為    左子數組的終點- 目前左子數組的目前指針
                count += mid+1-l;
                count %= 1000000007;
                // 臨時數組+1
                c++;
                // 右子數組的指針右移
                r++;
            }
        }

        // 左子數組還有元素時，全部放入臨時數組
        while(l <= mid)
            arr[c++] = array[l++];
        // 右子數組還有元素時，全部放入臨時數組
        while(r <= right)
            arr[c++] = array[r++];
        // 将臨時數組中的元素放入到原數組的指定位置
        for(int num:arr){
            array[s++] = num;
        }
    }
}