根据题目示例可以发现,顺时针打印矩阵的顺序是”从左向右,从上向下、从右向左、从下向上“循环
因此,考虑设定矩阵的”左、上、右、下“四个边界,模拟以上矩阵遍历顺序
算法流程:
class Solution { public int[] spiralOrder(int[][] matrix) { if(matrix.length == 0) return new int[0]; int l = 0; int r = matrix[0].length - 1; int t = 0; int b = matrix.length - 1; int x = 0; int[] arr = new int[(r+1)*(b+1)]; while(true) { for(int i = l; i <= r; i++) arr[x++] = matrix[t][i]; if(++t > b) break; for(int i = t; i <= b; i++) arr[x++] = matrix[i][r]; if(--r < l) break; for(int i = r; i >= l; i--) arr[x++] = matrix[b][i]; if(--b < t) break; for(int i = b; i >= t; i--) arr[x++] = matrix[i][l]; if(++l > r) break; } return arr; } }
可以将矩阵看成若干层,首先打印最外层的元素,其次打印次外层的元素,直到打印最内层的元素
定义矩阵的第 k 层是到最近边界距离为 k 的所有顶点。例如,下图矩阵最外层元素都是第 1 层,次外层元素都是第 2 层,剩下的元素都是第 3 层
[[1, 1, 1, 1, 1, 1, 1],
[1, 2, 2, 2, 2, 2, 1],
[1, 2, 3, 3, 3, 2, 1],
[1, 2, 2, 2, 2, 2, 1],
[1, 1, 1, 1, 1, 1, 1]]
对于每层,从左上方开始以顺时针的顺序遍历所有元素。假设当前层的左上角位于(top,left),右下角位于(bottom,right),按照如下顺序遍历当前层的元素
遍历完当前层的元素之后,将 left 和 top 分别增加 1,将 right 和 bottom 分别减少 1,进入下一层继续遍历,直到遍历完所有元素为止
class Solution { public int[] spiralOrder(int[][] matrix) { if(matrix.length == 0) return new int[0]; int rows = matrix.length; int columns = matrix[0].length; int[] arr = new int[columns * rows]; int l = 0; int t = 0; int r = columns - 1; int b = rows - 1; int x = 0; while(l <= r && t <= b){ for(int i = l; i <= r; i++){ arr[x++] = matrix[t][i]; } for(int i = t+1; i <= b; i++){ arr[x++] = matrix[i][r]; } //如果 l = r,或者 t = b,那就不需要执行下面了,只需要进行下一次 while 循环就能遍历完 if(l < r && t < b){ for(int i = r - 1; i > l; i--){ arr[x++] = matrix[b][i]; } for(int i = b; i > t; i--){ arr[x++] = matrix[i][l]; } } l++; t++; r--; b--; } return arr; } }