文章背景：

在複習(xí)演算法及資料結(jié)構(gòu)時(shí)，找到了面試筆試題目，以下我們來看看題目：

（學(xué)習(xí)影片分享：java教學(xué)影片）

在陣列中的兩個(gè)數(shù)字，如果前面一個(gè)數(shù)字大於後面的數(shù)字，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)Α］斎胍粋€(gè)數(shù)組,求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)P。並將P對1000000007取模的結(jié)果輸出。即輸出P 00000007

輸入描述:

題目保證輸入的數(shù)組中沒有的相同的數(shù)字

數(shù)據(jù)範(fàn)圍：

對於P的數(shù)據(jù),size<=10^4

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

對於 0的資料,size<=2*10^5

分析：

這題目很好直接求解，不過時(shí)間複雜度在o(n*n) ,?最開始拿到這題沒經(jīng)過思考，直接dp寫完了，然後發(fā)現(xiàn)，dp還不如直接求解，都是o(n*n)的複雜度，dp還佔(zhàn)用了2*10^5的空間，下面是直接，求法和dp ,都超時(shí)了。

（更多相關(guān)面試題推薦：java面試題目及答案）

#程式碼分享：

  //直接求法 ,超時(shí)
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{
 
  //一維數(shù)組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);
		} 
	}
}

相關(guān)推薦：java入門教程

以上是java面試之歸併排序的應(yīng)用的詳細(xì)內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！