0
146
VisualizaçõesBuscar en una matriz ordenada circularmente Java
Realmente me quedé atascado en esto y me encantaría tu ayuda.
Estoy tratando de escribir un método con la firma:
public static boolean search (int [][] mat, int num)El método obtiene como parámetros una matriz bidimensional ordenada circularmente y un valor para buscar num. Si el valor num está en la matriz mat, el método devuelve verdadero. Si el valor numérico no está en la matriz mat, el método devuelve falso.
La matriz es circular si todos los valores en el Trimestre 1 son realmente más pequeños que todos los del Trimestre 2, los del Trimestre 2 son realmente más pequeños que todos los del Trimestre 3, y los del Trimestre 3 son realmente más pequeños que todos los del Trimestre 4.
Por ejemplo, la siguiente matriz está ordenada circularmente:
Si la matriz mat es la matriz dibujada arriba y el número num es 22, el método devuelve el valor verdadero.
Si la matriz mat es la matriz dibujada arriba, y el número num es 23, el método devolverá el valor falso
Las condiciones:
- La matriz es bidimensional cuadrática, lo que significa que el número de filas y columnas es igual
- La matriz mat no es nula y está ordenada circularmente. No es necesario que verifique esto.
- El método debe ser lo más efectivo posible, tanto en términos de complejidad de tiempo como en términos de complejidad de memoria.
1 Respostas
Responde à pergunta0
La construcción de este tipo es tal que el elemento más pequeño de cada cuarto está arriba a la izquierda y el más grande está abajo a la izquierda. Puede comprobar en qué trimestre se debe ubicar el elemento buscado y repetir la búsqueda en sub-trimestres de ese trimestre.
Un ejemplo de implementación:
private static boolean search(int[][] mat, int num) { if (!square(mat)) { throw new IllegalArgumentException("matrix is not square"); } int dim = mat.length; int topRow = 0; int leftColumn = 0; while (dim > 1) { if (dim % 2 != 0) { throw new IllegalArgumentException("matrix dimension is not a power of two"); } int qdim = dim / 2; // quarter dimensions // Order of checks is important. if (num >= mat[topRow + qdim][leftColumn]) { // has to be in the bottom left quarter topRow += qdim; } else if (num >= mat[topRow + qdim][leftColumn + qdim]) { // has to be in the bottom right quarter topRow += qdim; leftColumn += qdim; } else if (num >= mat[topRow][leftColumn + qdim]) { // has to be in the top right quarter leftColumn += qdim; } // If all the conditions above give false, it's in the top left quarter // and topRow and leftColumn don't change. dim = qdim; } return mat[topRow][leftColumn] == num; }