Dada una matriz de mxn elementos (m filas, n columnas), devuelva todos los elementos de la matriz en orden espiral.
Por ejemplo, dada la siguiente matriz:
[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
Deberías regresar [1,2,3,6,9,8,7,4,5].
Solución Java 1
Si queda más de una fila y columna, puede formar un círculo y procesamos el círculo. De lo contrario, si solo queda una fila o columna, procesamos SOLAMENTE esa columna o fila.
public class Solution { public ArrayList<Integer> spiralOrder(int[][] matrix) { ArrayList<Integer> result = new ArrayList<Integer>(); if(matrix == null || matrix.length == 0) return result; int m = matrix.length; int n = matrix[0].length; int x=0; int y=0; while(m>0 && n>0){ //if one row/column left, no circle can be formed if(m==1){ for(int i=0; i<n; i++){ result.add(matrix[x][y++]); } break; }else if(n==1){ for(int i=0; i<m; i++){ result.add(matrix[x++][y]); } break; } //below, process a circle //top - move right for(int i=0;i<n-1;i++){ result.add(matrix[x][y++]); } //right - move down for(int i=0;i<m-1;i++){ result.add(matrix[x++][y]); } //bottom - move left for(int i=0;i<n-1;i++){ result.add(matrix[x][y--]); } //left - move up for(int i=0;i<m-1;i++){ result.add(matrix[x--][y]); } x++; y++; m=m-2; n=n-2; } return result; } } |
Del mismo modo, podemos escribir la solución de esta manera:
public List<Integer> spiralOrder(int[][] matrix) { List<Integer> result = new ArrayList<Integer>(); if(matrix==null||matrix.length==0||matrix[0].length==0) return result; int m = matrix.length; int n = matrix[0].length; int left=0; int right=n-1; int top = 0; int bottom = m-1; while(result.size()<m*n){ for(int j=left; j<=right; j++){ result.add(matrix[top][j]); } top++; for(int i=top; i<=bottom; i++){ result.add(matrix[i][right]); } right--; //prevent duplicate row if(bottom<top) break; for(int j=right; j>=left; j--){ result.add(matrix[bottom][j]); } bottom--; // prevent duplicate column if(right<left) break; for(int i=bottom; i>=top; i--){ result.add(matrix[i][left]); } left++; } return result; } |
Solución Java 2
También podemos resolver este problema de forma recursiva. El rendimiento de la solución no es mejor que el de la Solución 1. Por lo tanto, se debe preferir la Solución 1.
public class Solution { public ArrayList<Integer> spiralOrder(int[][] matrix) { if(matrix==null || matrix.length==0) return new ArrayList<Integer>(); return spiralOrder(matrix,0,0,matrix.length,matrix[0].length); } public ArrayList<Integer> spiralOrder(int [][] matrix, int x, int y, int m, int n){ ArrayList<Integer> result = new ArrayList<Integer>(); if(m<=0||n<=0) return result; //only one element left if(m==1&&n==1) { result.add(matrix[x][y]); return result; } //top - move right for(int i=0;i<n-1;i++){ result.add(matrix[x][y++]); } //right - move down for(int i=0;i<m-1;i++){ result.add(matrix[x++][y]); } //bottom - move left if(m>1){ for(int i=0;i<n-1;i++){ result.add(matrix[x][y--]); } } //left - move up if(n>1){ for(int i=0;i<m-1;i++){ result.add(matrix[x--][y]); } } if(m==1||n==1) result.addAll(spiralOrder(matrix, x, y, 1, 1)); else result.addAll(spiralOrder(matrix, x+1, y+1, m-2, n-2)); return result; } } |
