本文共 860 字，大约阅读时间需要 2 分钟。

题目描述

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

程序代码如下，其本质就是归并排序的基础上做一些修改。

public class Solution {    public int cnt=0;	public int[] temp;		//归并排序	public void mergeSort(int L, int R, int[] array)	{		if(L==R)		{			return;		}				int mid=(L+R)/2;		mergeSort(L,mid,array);		mergeSort(mid+1,R,array);		int left=mid;		int right=R;		for(int i=R;i>=L;i--)		{			if(left
   
    =array[right])   //左边部分的值大于右边部分的值			{								this.cnt=(this.cnt+(right-mid))%1000000007;      //这一步很重要								temp[i]=array[left];				left--;			}			else			{				temp[i]=array[right];				right--;			}		}				for(int i=L;i<=R;i++)		{			array[i]=temp[i];		}	}			public int InversePairs(int [] array) {				if(array.length==0)		{			return 0;		}		temp=new int[array.length];		mergeSort(0,array.length-1,array);		return cnt%1000000007;		    }}
   

转载地址：http://sckmi.baihongyu.com/