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%1000000007Description de l'entrée :La question garantit que le même nombre n'est pas dans le tableau d'entréePlage de données : Pour %50 données, taille<=10^4Pour %75 données, taille<=10^5Pour %100 données, taille<=2*10^5Analyse : 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; } } }
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; } } }
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!