En las entrevistas de algoritmo, a los entrevistadores siempre les gusta hacer artículos sobre listas vinculadas, clasificación, árboles binarios y búsqueda binaria, y la mayoría de las personas pueden seguir libros profesionales para memorizarlas. El entrevistador no quiere reclutar a un programador con buenas habilidades de memoria, pero no puede aprender y aplicarlo. Por lo tanto, es muy importante aprender a modelar y analizar problemas matemáticamente y usar algoritmos o estructuras de datos razonables para resolver problemas.
Pregunta de la entrevista: Imprima el número mínimo de la matriz giratoria
Título: Mueva los primeros elementos de una matriz al final de la matriz, que llamamos la rotación de la matriz. Ingrese una rotación de una matriz clasificada incrementalmente y emita el elemento mínimo de la matriz de rotación. Por ejemplo, la matriz {3, 4, 5, 1, 2} es una rotación de la matriz {1, 2, 3, 4, 5}, y el valor mínimo de la matriz es 1.
Para lograr este requisito, solo necesitamos atravesar la matriz, encontrar el valor más pequeño y salir del bucle directamente. La implementación del código es la siguiente:
public class test08 {public static int getThemin (int nums []) {if (nums == null || nums.length == 0) {Throw New RuntimeException ("¡Error de entrada!"); } int resultado = nums [0]; for (int i = 0; i <nums.length - 1; i ++) {if (nums [i + 1] <nums [i]) {result = nums [i + 1]; romper; }} Resultado de retorno; } public static void main (string [] args) {// entrada típica, una rotación de una matriz ascendente monotónica int [] array1 = {3, 4, 5, 1, 2}; System.out.println (getThemin (array1)); // Hay números duplicados, y el número más pequeño que es solo el número más pequeño int [] Array2 = {3, 4, 5, 1, 1, 2}; System.out.println (getThemin (array2)); // Hay números duplicados, pero los números duplicados no son los primeros y últimos números int [] Array3 = {3, 4, 5, 1, 2, 2}; System.out.println (getThemin (array3)); // Hay números duplicados, y los números duplicados son los primeros y últimos números int [] Array4 = {1, 0, 1, 1, 1}; System.out.println (getThemin (Array4)); // matriz ascendente monótona, rotar 0 elementos, es decir, la matriz ascendente monotónica en sí int [] array5 = {1, 2, 3, 4, 5}; System.out.println (getThemin (array5)); // Solo hay un número en la matriz int [] array6 = {2}; System.out.println (getThemin (array6)); // Los números en la matriz son los mismos int [] array7 = {1, 1, 1, 1, 1, 1, 1}; System.out.println (getThemin (Array7)); }}No hay nada de malo en la impresión de resultados. Sin embargo, este método obviamente no es el mejor. Veamos si hay una manera de encontrar un mejor método para lidiar con él.
Ordenado, ¿todavía necesitas buscar?
Cuando encontramos estas dos palabras clave, inevitablemente pensaremos en nuestro método de búsqueda binaria, pero muchos amigos definitivamente preguntarán que nuestra matriz ya no es una matriz verdaderamente ordenada después de ser rotada, pero es como una combinación de dos matrices incrementales. Podemos pensar así.
Podemos establecer dos subíndices de bajo y alto, y establecer Mid = (bajo + alto)/2, y naturalmente podemos encontrar la matriz de elementos [Mid] en el medio de la matriz. Si el elemento medio está en la matriz incremental en el frente, entonces debe ser mayor o igual al elemento correspondiente del subíndice bajo. En este momento, el elemento más pequeño en la matriz debe estar detrás del elemento. Podemos apuntar el subíndice bajo al elemento intermedio, que puede reducir el rango de búsquedas.
Del mismo modo, si el elemento intermedio se encuentra en la subrayada incremental posterior, debe ser menor o igual al elemento correspondiente al subíndice alto. En este momento, el elemento más pequeño en la matriz debe estar frente al elemento intermedio. Podemos actualizar el alto subíndice al subíndice mediano, que también puede reducir el rango de búsquedas. Los elementos correspondientes al subíndice alto después de mudarse aún están en la subrayada incremental posterior.
Ya sea que se actualice bajo o alto, nuestro rango de búsqueda se reducirá a la mitad del original. A continuación, utilizaremos el subíndice actualizado para repetir una nueva ronda de búsquedas. Hasta que los dos últimos subíndices estén adyacentes, es decir, nuestra condición final de bucle.
He dicho mucho, y parece que he estado en un desastre. También podríamos usar la entrada en la pregunta para simular y verificar nuestro algoritmo.
Echemos un vistazo a cómo implementar esta idea en Java usando el código:
public class test08 {public static int getThemin (int nums []) {if (nums == null || nums.length == 0) {Throw New RuntimeException ("¡Error de entrada!"); } // Si solo hay un elemento, regrese directamente si (nums.length == 1) return nums [0]; int resultado = nums [0]; int low = 0, alto = nums.length - 1; int Mid; // Asegúrese de que el valor correspondiente al subíndice bajo esté en la subarray de incremento a la izquierda, y el valor correspondiente a la alta se encuentra en la subarray de incremento a la derecha, mientras que (nums [bajo]> = nums [high]) {// asegura el extremo de la condición de bucle si (alto - bajo == 1) {devuelve nums [alto]; } // tomar la posición media mid = (baja + alta) / 2; // indica que el elemento medio se incrementa en la izquierda if (nums [mid]> = nums [low]) {Low = Mid; } else {high = mid; }} Resultado de retorno; } public static void main (string [] args) {// entrada típica, una rotación de una matriz ascendente monotónica int [] array1 = {3, 4, 5, 1, 2}; System.out.println (getThemin (array1)); // Hay números duplicados y el número más pequeño que solo repite los números es int [] array2 = {3, 4, 5, 1, 1, 2}; System.out.println (getThemin (array2)); // Hay números duplicados, pero los números duplicados no son los primeros y últimos números int [] Array3 = {3, 4, 5, 1, 2, 2}; System.out.println (getThemin (array3)); // Hay números duplicados, y los números duplicados son exactamente los primeros y últimos números int [] array4 = {1, 0, 1, 1, 1}; System.out.println (getThemin (Array4)); // matriz ascendente monótona, rotar 0 elementos, es decir, la matriz ascendente monótona en sí int [] array5 = {1, 2, 3, 4, 5}; System.out.println (getThemin (array5)); // Solo hay un número en la matriz int [] array6 = {2}; System.out.println (getThemin (array6)); // Los números en la matriz son los mismos int [] array7 = {1, 1, 1, 1, 1, 1, 1, 1}; System.out.println (getThemin (Array7)); // Especial No sé cómo mover int [] Array8 = {1, 0, 1, 1, 1}; System.out.println (getThemin (Array8)); }}Mencionamos anteriormente que en una matriz giratoria, ya que varios números en la matriz clasificada incrementalmente se mueven detrás de la matriz, el primer número siempre es mayor o igual al último número, y hay otro caso especial de que se mueven 0 elementos, es decir, la matriz en sí también es su propia matriz rotativa. Esta situación en sí misma está ordenada, por lo que solo necesitamos devolver el primer elemento, por lo que asigno el resultado a NUMS [0] primero.
¿Es el código anterior perfecto? No cumplimos con nuestros requisitos a través de los casos de prueba. Echemos un vistazo a la entrada de Array8 en detalle. Primero analicemos la operación de la computadora:
Pero podemos ver de un vistazo que nuestro valor mínimo no es 1, sino 0, por lo que cuando la matriz [baja], la matriz [Mid] y la matriz [alta] son iguales, nuestro programa no sabe cómo moverse. Según el método de movimiento actual, la matriz [MID] se incrementa a la izquierda de forma predeterminada. Esto es obviamente irresponsable.
Correcemos el código:
public class test08 {public static int getThemin (int nums []) {if (nums == null || nums.length == 0) {Throw New RuntimeException ("¡Error de entrada!"); } // Si solo hay un elemento, regrese directamente si (nums.length == 1) return nums [0]; int resultado = nums [0]; int low = 0, alto = nums.length - 1; int mid = bajo; // Asegúrese de que el valor correspondiente al subíndice bajo esté en la subarray de incremento a la izquierda, y el valor correspondiente a la alta se encuentra en la subarray de incremento a la derecha, mientras que (nums [bajo]> = nums [high]) {// asegura el extremo de la condición de bucle si (alto - bajo == 1) {devuelve nums [alto]; } // tomar la posición media mid = (baja + alta) / 2; // En casos especiales en los que los tres valores son iguales, debe encontrar el valor más pequeño de principio a fin if (nums [mid] == nums [low] && nums [mid] == nums [alto]) {return midInorder (nums, bajo, alto); } // indica que el elemento medio se incrementa en la izquierda if (nums [mid]> = nums [Low]) {Low = Mid; } else {high = mid; }} Resultado de retorno; } / *** Encuentre el valor mínimo en la matriz*** @param nums Array* @param Inicio Array Posición de inicio* @param End Array Posición de la matriz* @return El número más pequeño encontrado* / public static int midinorder (int [] nums, int inicio, int end) {int resultado = nums [inicio]; for (int i = inicio+1; i <= end; i ++) {if (resultado> nums [i]) resultado = nums [i]; } resultado de retorno; } public static void main (string [] args) {// entrada típica, una rotación de una matriz ascendente monotónica int [] array1 = {3, 4, 5, 1, 2}; System.out.println (getThemin (array1)); // Hay números duplicados y el número más pequeño que resulta ser el número más común int [] Array2 = {3, 4, 5, 1, 1, 2}; System.out.println (getThemin (array2)); // Hay números duplicados, pero los números duplicados no son el primer y último número int [] Array3 = {3, 4, 5, 1, 2, 2}; System.out.println (getThemin (array3)); // Hay números duplicados, y los números duplicados son exactamente el primer y último número int [] array4 = {1, 0, 1, 1, 1}; System.out.println (getThemin (Array4)); // matriz ascendente monótona, rotar 0 elementos, es decir, la matriz ascendente monótona en sí int [] array5 = {1, 2, 3, 4, 5}; System.out.println (getThemin (array5)); // Solo hay un número en la matriz int [] array6 = {2}; System.out.println (getThemin (array6)); // Todos los números en la matriz son los mismos int [] array7 = {1, 1, 1, 1, 1, 1, 1}; System.out.println (getThemin (Array7)); // Especial No sé cómo mover int [] Array8 = {1, 0, 1, 1, 1}; System.out.println (getThemin (Array8)); }}Luego lo colocamos con casos de prueba completos y la prueba pasa.
Resumir
De hecho, esta pregunta tiene muchos puntos para examinar, pero de hecho es examinar la aplicación flexible de la búsqueda binaria. Muchos amigos deben seguir las búsquedas binarias ordenadas sin aprender la idea de la búsqueda binaria, lo que llevará a pensar solo en los valores mínimos de búsqueda circular.
Muchos amigos hicieron una declaración durante la entrevista de que el ecosistema original de Android básicamente encapsulaba algoritmos comunes y protestaba contra estos algoritmos ineficaces en la entrevista. Esto es bastante estúpido. No buscamos implementar algoritmos de memoria, pero buscamos aprender las ideas inteligentes en él. Solo mejorando constantemente la capacidad de pensamiento de uno puede ayudar a uno a obtener un mejor desarrollo profesional.
Lo anterior es todo el contenido de este artículo. Espero que sea útil para el aprendizaje de todos y espero que todos apoyen más a Wulin.com.