Application du tri par fusion dans l'interview Java

Contexte de l'article :

En examinant les algorithmes et les structures de données, j'ai trouvé les questions du test écrit de l'entretien. Jetons un coup d'œil aux questions :

<.> (Apprendre le partage vidéo :

vidéo pédagogique Java)

Deux nombres dans le tableau, si le premier nombre est supérieur au dernier nombre, alors les deux nombres forment une paire d'ordre inverse . Saisissez un tableau et recherchez le nombre total de paires d’ordre inverse P dans le tableau. Et affichez le résultat de P modulo 1000000007. Autrement dit, sortie P%1000000007

Description de l'entrée :

La question garantit que le même nombre n'est pas dans le tableau d'entrée

Plage de données :

Pour %50 données, taille<=10^4

Pour %75 données, taille<=10^5

Pour %100 données, taille<=2*10^5

Analyse :

Cette question est facile à résoudre directement, mais la complexité temporelle est o(n*n). Quand j'ai reçu cette question pour la première fois, je n'y ai pas pensé, alors je viens de terminer. en l'écrivant via dp, puis j'ai découvert que dp était toujours disponible. Il est préférable de le résoudre directement, ce qui a une complexité de O(n*n), et dp prend également 2*10^5 d'espace. une solution directe. La méthode et dp ont expiré.

(Recommandations pour des questions d'entretien plus connexes :

questions et réponses d'entretien Java)

Partage de code :

  //直接求法 ,超时
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;
       }
       
   }
}

rrree

dp est redondant ici,

Voici le problème à résoudre par le tri par fusion. Si vous ne comprenez pas le tri par fusion, vous pouvez lire mon blog précédent

Tri par fusion :

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

Recommandations associées :

Tutoriel d'introduction à Java

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!