• 技术文章 >Java >Java面试题

    java面试之归并排序的应用

    VV2020-11-18 15:41:48转载51

    文章背景:

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

    (学习视频分享: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面试之归并排序的应用的详细内容,更多请关注php中文网其它相关文章!

    本文转载于:csdn,如有侵犯,请联系a@php.cn删除
    专题推荐:java 面试 归并排序
    上一篇:java面试中常见的数组题目汇总(五) 下一篇:java面试——慢查询
    第14期线上培训班

    相关文章推荐

    • PHP实现归并排序算法(代码实例)• 排序算法—归并排序【附代码】• 如何利用java实现归并排序• 归并排序有什么用

    全部评论我要评论

  • 取消发布评论发送
  • 1/1

    PHP中文网