剑指offer-数组中的逆序对详解编程语言

题目描述

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

输入描述

题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5

示例1

输入

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

输出

7

题解

可以用归并排序的思想来做，对数组进行二分递归，每次处理左右数组直到每个子数组只有两个元素，然后对这两个元素进行排序并计算逆序对。
关于归并排序可以看下我的一篇博客：IT虾米网
这样做的话，每次递归进行归并的两个子数组都是从小到大有序的。
这样只用从两个子数组的第一个进行比较，如果左>右，那么左游标之后的左数组都可以和右游标所指向的元素组成逆序对，如果左<右，那么左游标往右走就好了。注意在这个过程中，要维护一个合并两个子数组的数组，这样把两个子数组走完之后，直接用这个数组覆盖即可。

public class Solution {
    
    int cnt;	//记录逆序对总数 
    int[] temp;  //用于记录排序好的数组 
    private static final int mod = 1000000007; 
 
    public int InversePairs(int [] array) {
    
        int len = array.length; 
        if( len == 0 ) return 0; 
        cnt = 0; 
        temp = new int[len]; 
        merge(array, 0, len-1); 
        return cnt%mod; 
    } 
 
    public void merge(int[] a, int start, int end){
    
        if( start>=end ) return; 
        int mid = (start+end) >> 1; 
        merge(a, start, mid); 
        merge(a, mid+1, end); 
        mergeSub(a, start, mid, end); 
    } 
 
    public void mergeSub(int[] a, int start, int mid, int end){
    
        //存储排序后的数组 
        int i = start, j = mid+1; 
        int idx = 0; 
        while ( i<=mid && j<=end ){
    
            if( a[i]<a[j] ){
    
                temp[idx++] = a[i++]; 
            }else{
    
                temp[idx++] = a[j++]; 
                //左>右：从左游标到mid的元素都可以与右游标当前元素组成逆序对 
                cnt += (mid-i+1); 
                //数据量有点大，每次都要取一次 
                cnt %= mod; 
            } 
        } 
        //左边没到头，把左边剩余元素全部添加到已排序数组中 
        while( i<=mid ){
    
            temp[idx++] = a[i++]; 
        } 
        //同上 
        while( j<=end ){
    
            temp[idx++] = a[j++]; 
        } 
        //覆盖 
        for( int k=0; k<=(end-start); k++ ){
    
            a[start+k] = temp[k]; 
        } 
    } 
}