Javaインタビューでのマージソートの適用

記事の背景:

アルゴリズムとデータ構造を検討しているときに、面接の筆記試験の質問を見つけました。質問を見てみましょう:

(学習ビデオ共有: java 教育ビデオ )

配列内の 2 つの数値。前の数値が次の数値より大きい場合、2 つの数値は逆順のペアを形成します。 。配列を入力し、配列内の逆順ペアの総数 P を求めます。そして、P モジュロ 1000000007 の結果を出力します。つまり、出力 P 00000007

入力の説明:

質問により、同じ数値が入力配列に存在しないことが保証されます

データ範囲:

For 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 < array.length ; k ++)
        	   count[k] = 0;
       }
       
   }
    
}

dp はここでは冗長です。

マージ ソートの問題の解決策は次のとおりです。マージ ソートがわからない場合は、以前のブログを参照してください。MERGE SORT:

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 中国語 Web サイトの他の関連記事を参照してください。