Em entrevistas de algoritmo, os entrevistadores sempre gostam de fazer artigos sobre listas vinculadas, classificação, árvores binárias e pesquisa binária, e a maioria das pessoas pode seguir livros profissionais para memorizá -los. O entrevistador não deseja recrutar um programador com boas habilidades de memória, mas não pode aprender e aplicá -lo. Portanto, é muito importante aprender a modelar e analisar problemas matematicamente e usar algoritmos ou estruturas de dados razoáveis para resolver problemas.
Pergunta da entrevista: Imprima o número mínimo da matriz rotativa
Título: Mova os primeiros elementos de uma matriz para o final da matriz, que chamamos de rotação da matriz. Digite uma rotação de uma matriz classificada de forma incremental e produza o elemento mínimo da matriz de rotação. Por exemplo, a matriz {3, 4, 5, 1, 2} é uma rotação da matriz {1, 2, 3, 4, 5}, e o valor mínimo da matriz é 1.
Para atingir esse requisito, precisamos apenas atravessar a matriz, encontrar o menor valor e sair diretamente do loop. A implementação do código é a seguinte:
public class Test08 {public static int getThemin (int nums []) {if (nums == null || nums.Length == 0) {lança a nova RuntimeException ("Erro de entrada!"); } int resultado = nums [0]; for (int i = 0; i <nums.Length - 1; i ++) {if (nums [i + 1] <nums [i]) {resultado = nums [i + 1]; quebrar; }} Retornar resultado; } public static void main (string [] args) {// entrada típica, uma rotação de uma matriz ascendente monotônica int [] array1 = {3, 4, 5, 1, 2}; System.out.println (getThemin (Array1)); // Existem números duplicados e o menor número que é apenas o menor número int [] array2 = {3, 4, 5, 1, 1, 2}; System.out.println (getThemin (Array2)); // Existem números duplicados, mas os números duplicados não são os primeiros e os últimos números int [] array3 = {3, 4, 5, 1, 2, 2}; System.out.println (getThemin (Array3)); // Existem números duplicados, e os números duplicados são os primeiros e os últimos números int [] array4 = {1, 0, 1, 1, 1}; System.out.println (getThemin (Array4)); // Matriz ascendente monótona, gire 0 elementos, ou seja, a própria matriz ascendente monotônica int [] array5 = {1, 2, 3, 4, 5}; System.out.println (getThemin (Array5)); // existe apenas um número na matriz int [] array6 = {2}; System.out.println (getThemin (Array6)); // Os números na matriz são os mesmos int [] array7 = {1, 1, 1, 1, 1, 1, 1}; System.out.println (getThemin (Array7)); }}Não há nada de errado com os resultados da impressão. No entanto, esse método obviamente não é o melhor. Vamos ver se existe uma maneira de encontrar um método melhor para lidar com isso.
Ordenado, ainda precisa pesquisar?
Quando encontrarmos essas duas palavras -chave, inevitavelmente pensaremos em nosso método de pesquisa binária, mas muitos amigos definitivamente pedirão que nossa matriz não seja mais uma matriz verdadeiramente ordenada após serem giradas, mas é como uma combinação de duas matrizes incrementais. Podemos pensar assim.
Podemos definir dois subscritos baixos e altos e definir MID = (baixo + alto)/2, e podemos encontrar naturalmente a matriz de elementos [no meio] no meio da matriz. Se o elemento médio estiver na matriz incremental na frente, deve ser maior ou igual ao elemento correspondente do baixo subscrito. Neste momento, o menor elemento da matriz deve estar por trás do elemento. Podemos apontar o baixo subscrito para o elemento intermediário, que pode restringir o intervalo de pesquisas.
Da mesma forma, se o elemento intermediário estiver localizado no subarray incremental subsequente, ele deve ser menor ou igual ao elemento correspondente ao alto subscrito. Nesse momento, o menor elemento da matriz deve estar em frente ao elemento intermediário. Podemos atualizar o alto subscrito para o subscrito mediano, que também pode restringir o intervalo de pesquisas. Os elementos correspondentes ao alto subscrito após a movimentação ainda estão no sub -aviso incremental subsequente.
Seja atualizando baixo ou alto, nosso intervalo de pesquisa será reduzido para metade do original. Em seguida, usaremos o subscrito atualizado para repetir uma nova rodada de pesquisas. Até que os dois últimos subscritos sejam adjacentes, ou seja, nossa condição final de loop.
Eu disse muito, e parece que estive em uma bagunça. Podemos também usar a entrada na pergunta para simular e verificar nosso algoritmo.
Vamos dar uma olhada em como implementar essa ideia em Java usando o código:
public class Test08 {public static int getThemin (int nums []) {if (nums == null || nums.Length == 0) {lança a nova RuntimeException ("Erro de entrada!"); } // Se houver apenas um elemento, retorne diretamente se (nums.Length == 1) retorna nums [0]; int resultado = nums [0]; int low = 0, alta = nums.Length - 1; int mid; // Verifique se o valor correspondente ao baixo subscrito está na subarray de incremento à esquerda, e o valor correspondente à alta está no subarray de incremento à direita, enquanto (nums [baixo]> = nums [alto]) {// verifique se o final da condição de loop se (alto - baixo == 1) {retorno nums [alto]; } // Pegue a posição intermediária média = (baixa + alta) / 2; // indica que o elemento intermediário é incrementado à esquerda se (nums [MID]> = nums [baixo]) {low = MID; } else {High = MID; }} Retornar resultado; } public static void main (string [] args) {// entrada típica, uma rotação de uma matriz ascendente monotônica int [] array1 = {3, 4, 5, 1, 2}; System.out.println (getThemin (Array1)); // Existem números duplicados e o menor número que apenas repete os números é int [] array2 = {3, 4, 5, 1, 1, 2}; System.out.println (getThemin (Array2)); // Existem números duplicados, mas os números duplicados não são os primeiros e os últimos números int [] array3 = {3, 4, 5, 1, 2, 2}; System.out.println (getThemin (Array3)); // Existem números duplicados, e os números duplicados são exatamente os primeiros e os últimos números int [] array4 = {1, 0, 1, 1, 1}; System.out.println (getThemin (Array4)); // Matriz ascendente monótona, gire 0 elementos, ou seja, a própria matriz ascendente monótona int [] array5 = {1, 2, 3, 4, 5}; System.out.println (getThemin (Array5)); // existe apenas um número na matriz int [] array6 = {2}; System.out.println (getThemin (Array6)); // Os números na matriz são os mesmos int [] array7 = {1, 1, 1, 1, 1, 1, 1, 1, 1}; System.out.println (getThemin (Array7)); // Especial, não sei como mover int [] array8 = {1, 0, 1, 1, 1}; System.out.println (getThemin (Array8)); }}Mencionamos anteriormente que em uma matriz rotativa, uma vez que vários números na matriz classificada de forma incremental são movidos atrás da matriz, o primeiro número é sempre maior ou igual ao último número, e há outro caso especial de que 0 elementos são movidos, ou seja, a matriz em si também é sua própria matriz rotativa. Essa situação é ordenada, então precisamos apenas retornar o primeiro elemento, e é por isso que atribuo o resultado a NUMS [0] primeiro.
O código acima é perfeito? Não atendemos aos nossos requisitos através dos casos de teste. Vamos dar uma olhada na entrada do Array8 em detalhes. Vamos primeiro analisar a operação do computador:
Mas podemos ver de relance que nosso valor mínimo não é 1, mas 0, portanto, quando a matriz [baixa], a matriz [mid] e a matriz [alta] são iguais, nosso programa não sabe como se mover. De acordo com o método de movimento atual, a matriz [MID] é incrementada à esquerda por padrão. Isso é obviamente irresponsável.
Vamos corrigir o código:
public class Test08 {public static int getThemin (int nums []) {if (nums == null || nums.Length == 0) {lança a nova RuntimeException ("Erro de entrada!"); } // Se houver apenas um elemento, retorne diretamente se (nums.Length == 1) retorna nums [0]; int resultado = nums [0]; int low = 0, alta = nums.Length - 1; int mid = baixo; // Verifique se o valor correspondente ao baixo subscrito está na subarray de incremento à esquerda, e o valor correspondente à alta está no subarray de incremento à direita, enquanto (nums [baixo]> = nums [alto]) {// verifique se o final da condição de loop se (alto - baixo == 1) {retorno nums [alto]; } // Pegue a posição intermediária média = (baixa + alta) / 2; // Em casos especiais em que os três valores são iguais, você precisa encontrar o menor valor do começo ao fim se (nums [mid] == nums [baixo] && nums [mid] == nums [alta]) {return midinomer (nums, baixo, alto); } // indica que o elemento médio é incrementado à esquerda se (nums [MID]> = nums [baixo]) {low = MID; } else {High = MID; }} Retornar resultado; } / *** Encontre o valor mínimo na matriz** @param nums Array* @param Iniciar a posição inicial Posição* @param Posição final da matriz final* @RETURN O menor número encontrado* / public static int MidinOrder (int [] nums, int start) {int resultado = nums [start]; for (int i = start+1; i <= end; i ++) {if (resultado> nums [i]) resultado = nums [i]; } resultado de retorno; } public static void main (string [] args) {// entrada típica, uma rotação de uma matriz ascendente monotônica int [] array1 = {3, 4, 5, 1, 2}; System.out.println (getThemin (Array1)); // Existem números duplicados e o menor número que por acaso é o número mais comum int [] array2 = {3, 4, 5, 1, 1, 2}; System.out.println (getThemin (Array2)); // Existem números duplicados, mas os números duplicados não são os primeiros e os últimos números int [] array3 = {3, 4, 5, 1, 2, 2}; System.out.println (getThemin (Array3)); // Existem números duplicados, e os números duplicados são exatamente os primeiros e os últimos números int [] array4 = {1, 0, 1, 1, 1}; System.out.println (getThemin (Array4)); // Matriz ascendente monótona, gire 0 elementos, ou seja, a própria matriz ascendente monótona int [] array5 = {1, 2, 3, 4, 5}; System.out.println (getThemin (Array5)); // existe apenas um número na matriz int [] array6 = {2}; System.out.println (getThemin (Array6)); // Todos os números na matriz são os mesmos int [] array7 = {1, 1, 1, 1, 1, 1, 1}; System.out.println (getThemin (Array7)); // Especial, não sei como mover int [] array8 = {1, 0, 1, 1, 1}; System.out.println (getThemin (Array8)); }}Em seguida, colocamos -o com casos de teste completos e o teste passa.
Resumir
De fato, essa pergunta tem muitos pontos a serem examinados, mas, de fato, é examinar a aplicação flexível da pesquisa binária. Muitos amigos devem seguir as pesquisas binárias ordenadas sem aprender a idéia de pesquisa binária, o que levará apenas a pensar em valores mínimos de pesquisa circular.
Muitos amigos fizeram uma declaração durante a entrevista de que o ecossistema original do Android basicamente encapsulou algoritmos comuns e protestou contra esses algoritmos ineficazes na entrevista. Isso é realmente muito estúpido. Não procuramos implementar algoritmos rotineiros, mas procuramos aprender as idéias inteligentes nele. Somente melhorando constantemente a capacidade de pensamento pode ajudar alguém a obter melhor desenvolvimento de carreira.
O exposto acima é todo o conteúdo deste artigo. Espero que seja útil para o aprendizado de todos e espero que todos apoiem mais o wulin.com.