java面試之歸併排序的應用

文章背景：

在複習演算法及資料結構時，找到了面試筆試題目，以下我們來看看題目：

（學習影片分享：java教學影片）

在陣列中的兩個數字，如果前面一個數字大於後面的數字，則這兩個數字組成一個逆序對。輸入一個數組,求出這個數組中的逆序對的總數P。並將P對1000000007取模的結果輸出。即輸出P 00000007

輸入描述:

題目保證輸入的數組中沒有的相同的數字

數據範圍：

對於P的數據,size<=10^4

對於u的資料,size<=10^5

對於 0的資料,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中文網其他相關文章！