java面试之归并排序的应用

文章背景：

在复习算法及数据结构时，找到了面试笔试题目，下面我们来看看题目：

（学习视频分享：java教学视频）

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

输入描述:

题目保证输入的数组中没有的相同的数字

数据范围：

对于%50的数据,size<=10^4

对于%75的数据,size<=10^5

对于%100的数据,size<=2*10^5

分析：

这道题目很好直接求解，不过时间复杂度在o(n*n) , 最开始拿到这题没经过思考，直接dp写完了，然后发现，dp还不如直接求解，都是o(n*n)的复杂度，dp还占用了2*10^5的空间，下面是直接，求法和dp ,都超时了。

（更多相关面试题推荐：java面试题及答案）

代码分享：

  //直接求法 ,超时 public  class solution{    public static  int sum;        public static int InversePairs(int [] array) {         dp(array);         return sum;    }          public static void dp(int []array){        for(int i = array.length - 1 ; i >  0 ; i --){            for(int j = i - 1 ; j >= 0 ; j--){                 if(array[j] > array[i]){                 	sum += 1;                 }             }            sum %= 1000000007;        }            } }

public  class solution{     //一维数组dp       public static  int sum;        public static int InversePairs(int [] array) {         dp(array);         return sum;    }    public static int count[] = new int[200004];        public static void dp(int []array){        for(int i = array.length - 1 ; i >  0 ; i --){            for(int j = i - 1 ; j >= 0 ; j--){                 if(array[j] > array[i]){                 	count[j] = count[j+1]+1;                 }else {                 	count[j] = count[j+1];                 }            }            sum += count[0];            sum %= 1000000007;            for(int k = 0 ; k < array.length ; k ++)         	   count[k] = 0;        }            }      }

dp在这里都是多余的，

下面是归并排序解决问题，不了解归并排序可以看我前一篇博客 归并排序：

public class solution{        //归并排序AC     public static int  cnt ;          public static  int InversePairs(int [] array) {                   if(array != null){              RecusionSorted(array,0,array.length - 1);         }         return  cnt%1000000007;     }	 	 	public static void MegerArray(int[] data, int start, int mid, int end) { 		 int temp[] = new int[end-start+1];  		 int i  =  mid; 		 int j = end; 		 int m = mid+1; 		 int z = 0; 		 while(j >= m && i >= start) { 			 if(data[i] > data[j]) { 				 temp[z++] = data[i--]; 				 cnt += (j-mid)%1000000007;                  cnt %= 1000000007; 			 }else { 				 temp[z++] = data[j--]; 			 } 		 } 		  		 while(j >= m) { 			 temp[z++] = data[j--]; 		 } 		 		 while(i >= start) { 			 temp[z++] = data[i--]; 		 } 		  		 for(int k = start ; k <= end ; k ++) { 			 data[k] = temp[end - k]; 		 } 	} 	 	public static void RecusionSorted(int data[] , int start , int end ) { 		 		 		if(start < end) { 			int mid = (start + end) >> 1; 			RecusionSorted(data,start,mid); 			RecusionSorted(data,mid+1,end); 		    MegerArray(data,start,mid,end); 		}  	} }

相关推荐：java入门教程

以上就是java面试之归并排序的应用的详细内容，更多内容请关注技术你好其它相关文章！