Dans les interviews d'algorithmes, les intervieweurs aiment toujours faire des articles autour des listes liées, du tri, des arbres binaires et de la recherche binaire, et la plupart des gens peuvent suivre des livres professionnels pour les mémoriser. L'intervieweur ne veut pas recruter un programmeur avec de bonnes compétences en mémoire mais ne peut pas l'apprendre et l'appliquer. Par conséquent, il est très important d'apprendre à modéliser et à analyser les problèmes mathématiquement et à utiliser des algorithmes ou des structures de données raisonnables pour résoudre les problèmes.
Question d'entrevue: imprimez le nombre minimum du tableau rotatif
Titre: Déplacez les premiers éléments d'un tableau à la fin du tableau, que nous appelons la rotation du tableau. Entrez une rotation d'un tableau trié progressivement et sortez l'élément minimum du tableau de rotation. Par exemple, le tableau {3, 4, 5, 1, 2} est une rotation du tableau {1, 2, 3, 4, 5}, et la valeur minimale du tableau est 1.
Pour atteindre cette exigence, nous avons juste besoin de traverser le tableau, de trouver la plus petite valeur et de quitter directement la boucle. L'implémentation du code est la suivante:
classe publique test08 {public static int getthemin (int nums []) {if (nums == null || nums.length == 0) {throw new RuntimeException ("Error d'entrée!"); } int résultat = nums [0]; for (int i = 0; i <nums.length - 1; i ++) {if (nums [i + 1] <nums [i]) {result = nums [i + 1]; casser; }} Retour Résultat; } public static void main (String [] args) {// Entrée typique, une rotation d'un tableau ascendant monotonique int [] array1 = {3, 4, 5, 1, 2}; System.out.println (getthemin (array1)); // Il y a des nombres en double, et le plus petit nombre qui n'est que le plus petit nombre int [] array2 = {3, 4, 5, 1, 1, 2}; System.out.println (getthemin (array2)); // il y a des nombres en double, mais les nombres en double ne sont pas les premier et dernier nombres int [] array3 = {3, 4, 5, 1, 2, 2}; System.out.println (getthemin (array3)); // il y a des nombres en double, et les nombres en double sont les premiers et derniers nombres int [] array4 = {1, 0, 1, 1, 1}; System.out.println (getthemin (array4)); // Array ascendant monotone, tournant 0 éléments, c'est-à-dire le tableau ascendant monotone lui-même int [] array5 = {1, 2, 3, 4, 5}; System.out.println (getthemin (array5)); // il n'y a qu'un seul numéro dans le tableau int [] array6 = {2}; System.out.println (getthemin (array6)); // Les nombres dans le tableau sont le même int [] array7 = {1, 1, 1, 1, 1, 1, 1}; System.out.println (getthemin (array7)); }}Il n'y a rien de mal aux résultats de l'impression. Cependant, cette méthode n'est évidemment pas la meilleure. Voyons s'il existe un moyen de trouver une meilleure méthode pour y faire face.
Ordrement, il faut toujours rechercher?
Lorsque nous trouvons ces deux mots clés, nous penserons inévitablement à notre méthode de recherche binaire, mais de nombreux amis nous demanderont certainement que notre tableau n'est plus un tableau vraiment commandé après avoir été tourné, mais c'est comme une combinaison de deux tableaux incrémentiels. Nous pouvons penser comme ça.
Nous pouvons définir deux indices bas et haut, et régler le milieu = (faible + haut) / 2, et nous pouvons naturellement trouver le tableau d'éléments [MID] au milieu du tableau. Si l'élément central se trouve dans le tableau incrémentiel devant, il doit être supérieur ou égal à l'élément correspondant de l'indice bas. À l'heure actuelle, le plus petit élément du tableau doit être derrière l'élément. Nous pouvons pointer l'indice bas vers l'élément intermédiaire, qui peut réduire la plage de recherches.
De même, si l'élément intermédiaire est situé dans le sous-réseau incrémentiel ultérieur, il doit être inférieur ou égal à l'élément correspondant à l'indice élevé. À l'heure actuelle, le plus petit élément du tableau doit être devant l'élément intermédiaire. Nous pouvons mettre à jour l'indice élevé de l'indice médian, qui peut également réduire la plage de recherches. Les éléments correspondant à l'indice élevé après le déménagement sont toujours dans le sous-réseau incrémentiel ultérieur.
Qu'il s'agisse de mettre à jour bas ou haut, notre plage de recherche sera réduite à la moitié de l'original. Ensuite, nous utiliserons l'indice mis à jour pour répéter une nouvelle série de recherches. Jusqu'à ce que les deux derniers indices soient adjacents, c'est-à-dire notre condition de fin de boucle.
J'ai beaucoup dit, et il semble que j'ai été en désordre. Nous pourrions aussi bien utiliser l'entrée dans la question pour simuler et vérifier notre algorithme.
Jetons un œil à la façon de mettre en œuvre cette idée en Java en utilisant le code:
classe publique test08 {public static int getthemin (int nums []) {if (nums == null || nums.length == 0) {throw new RuntimeException ("Error d'entrée!"); } // s'il n'y a qu'un seul élément, renvoie directement if (nums.length == 1) renvoie nums [0]; Int result = nums [0]; int low = 0, high = nums.length - 1; int mid; // Assurez-vous que la valeur correspondant à l'indice faible est dans le sous-tableau d'incrément à gauche, et la valeur correspondant au haut est dans le sous-tableau d'incrément à droite (nums [Low]> = nums [High]) {// assure la fin de la condition de boucle si (élevé - Low == 1) {return nums [haut]; } // Prenez la position centrale au milieu = (faible + haut) / 2; // indique que l'élément central est incrémenté sur la gauche if (nums [mid]> = nums [Low]) {Low = mid; } else {high = mid; }} Retour Résultat; } public static void main (String [] args) {// Entrée typique, une rotation d'un tableau ascendant monotonique int [] array1 = {3, 4, 5, 1, 2}; System.out.println (getthemin (array1)); // Il y a des nombres en double et le plus petit nombre qui répète simplement les nombres est int [] array2 = {3, 4, 5, 1, 1, 2}; System.out.println (getthemin (array2)); // il y a des nombres en double, mais les nombres en double ne sont pas les premier et dernier nombres int [] array3 = {3, 4, 5, 1, 2, 2}; System.out.println (getthemin (array3)); // il y a des nombres en double, et les nombres en double sont exactement les premier et derniers nombres int [] array4 = {1, 0, 1, 1, 1}; System.out.println (getthemin (array4)); // tableau ascendant monotone, tournant 0 éléments, c'est-à-dire le tableau ascendant monotone lui-même int [] array5 = {1, 2, 3, 4, 5}; System.out.println (getthemin (array5)); // il n'y a qu'un seul numéro dans le tableau int [] array6 = {2}; System.out.println (getthemin (array6)); // Les nombres dans le tableau sont le même int [] array7 = {1, 1, 1, 1, 1, 1, 1, 1}; System.out.println (getthemin (array7)); // spécial je ne sais pas comment déplacer int [] array8 = {1, 0, 1, 1, 1}; System.out.println (getthemin (array8)); }}Nous avons mentionné plus tôt que dans un tableau rotatif, puisque plusieurs nombres dans le tableau trié progressivement sont déplacés derrière le tableau, le premier nombre est toujours supérieur ou égal au dernier nombre, et il y a un autre cas particulier que 0 éléments est déplacé, c'est-à-dire que le tableau lui-même est également son propre tableau rotatif. Cette situation elle-même est commandée, nous avons donc juste besoin de retourner le premier élément, c'est pourquoi j'attribue d'abord le résultat à NUMS [0].
Le code ci-dessus est-il parfait? Nous n'avons pas répondu à nos exigences à travers les cas de test. Jetons un coup d'œil à l'entrée Array8 en détail. Analysons d'abord le fonctionnement de l'ordinateur:
Mais nous pouvons voir en un coup d'œil que notre valeur minimale n'est pas 1, mais 0, donc lorsque le tableau [bas], le tableau [mid] et le tableau [haut] sont égaux, notre programme ne sait pas comment bouger. Selon la méthode de mouvement actuelle, le tableau [mid] est incrémenté à gauche par défaut. C'est évidemment irresponsable.
Corrigeons le code:
classe publique test08 {public static int getthemin (int nums []) {if (nums == null || nums.length == 0) {throw new RuntimeException ("Error d'entrée!"); } // s'il n'y a qu'un seul élément, renvoie directement if (nums.length == 1) renvoie nums [0]; Int result = nums [0]; int low = 0, high = nums.length - 1; int mid = bas; // Assurez-vous que la valeur correspondant à l'indice faible est dans le sous-tableau d'incrément à gauche, et la valeur correspondant au haut est dans le sous-tableau d'incrément à droite (nums [Low]> = nums [High]) {// assure la fin de la condition de boucle si (élevé - Low == 1) {return nums [haut]; } // Prenez la position centrale au milieu = (faible + haut) / 2; // Dans les cas spéciaux où les trois valeurs sont égales, vous devez trouver la plus petite valeur du début à la fin if (nums [mid] == nums [Low] && nums [mid] == nums [high]) {return midinorder (nums, bas, high); } // indique que l'élément central est incrémenté sur la gauche if (nums [mid]> = nums [Low]) {Low = mid; } else {high = mid; }} Retour Résultat; } / ** * Trouvez la valeur minimale dans le tableau * * @param nums Array * @param start Array Position de démarrage * @param end Array End Position * @return Le plus petit nombre trouvé * / public static int Midinorder (int [] nums, int start, int end) {int résultat = nums [start]; for (int i = start + 1; i <= end; i ++) {if (result> nums [i]) result = nums [i]; } Retour Résultat; } public static void main (String [] args) {// Entrée typique, une rotation d'un tableau ascendant monotonique int [] array1 = {3, 4, 5, 1, 2}; System.out.println (getthemin (array1)); // Il y a des nombres en double et le plus petit nombre qui se trouve être le nombre le plus courant int [] array2 = {3, 4, 5, 1, 1, 2}; System.out.println (getthemin (array2)); // il y a des nombres en double, mais les nombres en double ne sont pas les premier et dernier nombres int [] array3 = {3, 4, 5, 1, 2, 2}; System.out.println (getthemin (array3)); // il y a des nombres en double, et les nombres en double sont exactement les premier et derniers nombres int [] array4 = {1, 0, 1, 1, 1}; System.out.println (getthemin (array4)); // tableau ascendant monotone, tournant 0 éléments, c'est-à-dire le tableau ascendant monotone lui-même int [] array5 = {1, 2, 3, 4, 5}; System.out.println (getthemin (array5)); // il n'y a qu'un seul numéro dans le tableau int [] array6 = {2}; System.out.println (getthemin (array6)); // Tous les nombres du tableau sont le même int [] array7 = {1, 1, 1, 1, 1, 1, 1}; System.out.println (getthemin (array7)); // spécial je ne sais pas comment déplacer int [] array8 = {1, 0, 1, 1, 1}; System.out.println (getthemin (array8)); }}Nous le mettons ensuite avec des cas de test complets et le test passe.
Résumer
En fait, cette question a de nombreux points à examiner, mais en fait, il s'agit d'examiner l'application flexible de la recherche binaire. De nombreux amis doivent suivre des recherches binaires ordonnées sans apprendre l'idée de recherche binaire, ce qui conduira uniquement à penser aux valeurs minimales de recherche circulaire.
De nombreux amis ont fait une déclaration lors de l'entretien que l'écosystème original Android a essentiellement encapsulé les algorithmes communs et protesté contre ces algorithmes inefficaces dans l'entretien. C'est en fait assez stupide. Nous ne cherchons pas à mettre en œuvre des algorithmes par cœur, mais nous cherchons à apprendre les idées intelligentes. Ce n'est qu'en améliorant constamment sa capacité de pensée que l'on peut aider à obtenir un meilleur développement de carrière.
Ce qui précède est tout le contenu de cet article. J'espère que cela sera utile à l'apprentissage de tous et j'espère que tout le monde soutiendra davantage Wulin.com.