本文共 944 字,大约阅读时间需要 3 分钟。
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数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
1、实际上是进行一次归并排序,先将分组定为1,前后比较,12比较,34比较、56比较,70比较,结束结果为1,2,3,4,5,6,0,7,此时结果res已经为12、将分组定为2,1234进行比较,5607进行比较,结束结果为1,2,3,4,0,5,6,7,此时res结果为1+2=33、将分组定位4,12340567进行比较,结束结果为0,1,2,3,4,5,6,7,此时res结果为3+4=74、需要注意的是在题目分割数组的时候,不一定都是2的幂次方,所以需要调整array1和array2数组的大小
public class Solution { int res=0; public int InversePairs(int [] array) { int start=0; int len = array.length; for(int i=1;;i*=2){ if (i>len) break;// System.out.println("i此时的数值为"+i); for(int x=0;xlen) l=len-x; int[] array1= new int[l]; int j=x; start=j; for(int k=0;k len) m=len-j; int[] array2= new int[m]; for(int k=0;k
转载地址:http://ngcqb.baihongyu.com/