Anwendung der Zusammenführungssortierung in Java-Interviews

Hintergrund des Artikels:

Beim Durchsehen von Algorithmen und Datenstrukturen habe ich die im Interview geschriebenen Testfragen gefunden:

(Teilen von Lernvideos: Java-Lehrvideo)

In Das Array aus zwei Zahlen. Wenn die vorherige Zahl größer als die folgende Zahl ist, bilden die beiden Zahlen ein Paar in umgekehrter Reihenfolge. Geben Sie ein Array ein und ermitteln Sie die Gesamtzahl der Paare P in umgekehrter Reihenfolge im Array. Und geben Sie das Ergebnis von P modulo 1000000007 aus. Das heißt, Ausgabe P%1000000007

Eingabebeschreibung:

Die Frage stellt sicher, dass sich nicht dieselbe Zahl im Eingabearray befindet

Datenbereich:

Für %50 Daten, Größe<=10^4

Für %75 Daten, Größe<=10^5

Für %100 Daten, Größe<=2*10^5

Analyse:

Diese Frage lässt sich leicht direkt lösen, aber die Zeitkomplexität beträgt o(n*n), at Der Anfang Als ich diese Frage bekam, schrieb ich sie direkt in dp, ohne darüber nachzudenken. Dann stellte ich fest, dass dp nicht so gut ist wie die direkte Lösung. Die Komplexität beträgt auch 2*10 ^5 Leerzeichen. Das Folgende ist direkt: Sowohl die Methode als auch dp haben eine Zeitüberschreitung.

(Empfehlungen für weitere verwandte Interviewfragen: Java-Interviewfragen und -antworten)

Codefreigabe:

  //直接求法 ,超时
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 ist hier überflüssig.

Das Folgende ist eine Lösung für die Zusammenführungssortierung. Wenn Sie die Zusammenführungssortierung nicht verstehen, Sie können mich sehen. Vorheriger Blog Merge-Sortierung:

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);
		} 
	}
}

Verwandte Empfehlungen: Java-Einführungs-Tutorial

Das obige ist der detaillierte Inhalt vonAnwendung der Zusammenführungssortierung in Java-Interviews. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!