剑指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]; 
} 
} 
}