Heim > Java > JavaInterview Fragen > Hauptteil

Anwendung der Zusammenführungssortierung in Java-Interviews

王林
Freigeben: 2020-11-18 15:41:48
nach vorne
2201 Leute haben es durchsucht

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;
       }
       
   }
}
Nach dem Login kopieren
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;
       }
       
   }
    
}
Nach dem Login kopieren

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);
		} 
	}
}
Nach dem Login kopieren

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!

Verwandte Etiketten:
Quelle:csdn.net
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage
Über uns Haftungsausschluss Sitemap
Chinesische PHP-Website:Online-PHP-Schulung für das Gemeinwohl,Helfen Sie PHP-Lernenden, sich schnell weiterzuentwickeln!