Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
Given the following matrix:
[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
You should return
[1,2,3,6,9,8,7,4,5]
.
Take this square as an example. Let's only look at the row for now. Because we goes in the order 0 -> 11 -> 2 -> 10 -> ... -> 5 ->6, so we always stops at the middle. It is the same with columns. Besides, if there is only one row or one column left (e.g., 3 by 3 matrix), we need to stop at the middle.
public class SpiralMatrix { public ArrayListspiralOrder(int[][] matrix) { ArrayList rst = new ArrayList (); if (matrix == null || matrix.length == 0) return rst; int rows = matrix.length; int cols = matrix[0].length; int count = 0; //Need to use 2 * count instead of rows / 2 //Otherwise will not work for rows or cols that are odd numbers while (2 * count < rows && 2 * count < cols) { for (int j = count; j < cols - count; j++) rst.add(matrix[count][j]); for (int i = count + 1; i < rows - count; i++) rst.add(matrix[i][cols - count - 1]); if (2 * count == rows - 1 || 2 * count == cols - 1) break; for (int j = cols - count - 2; j >= count; j--) rst.add(matrix[rows - 1 - count][j]); for (int i = rows - 2 - count; i > count; i--) rst.add(matrix[i][count]); count++; } return rst; } }
No comments:
Post a Comment