java面试之归并排序的应用

文章背景：

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

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

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

立即学习“Java免费学习笔记（深入）”；

输入描述:

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

数据范围：

对于P的数据,size

对于u的数据,size

对于0的数据,size

分析：

这道题目很好直接求解，不过时间复杂度在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 
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  cnt00000007;
    } 
 
 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)00000007;
                 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 > 1;
   RecusionSorted(data,start,mid);
   RecusionSorted(data,mid+1,end);
      MegerArray(data,start,mid,end);
  } 
 }
}
 登录后复制 
相关推荐：java入门教程
 
以上就是java面试之归并排序的应用的详细内容，更多请关注慧达安全导航其它相关文章！