54. 螺旋矩阵

题目链接

分析

跟 59. 螺旋矩阵 II 相比，其实没什么差别，无非就是需要处理只有一横或者只有一竖的场景，其实这样很好处理，这样就不需要考虑到了边界转圈这些情况了，直接按一唯数组遍历即可。而且此时 rowNow 和 colNow 都不需要换。

方向向量法

我们可以直接参考 59. 螺旋矩阵 II#方向向量法 来遍历矩阵，

• 初始坐标在矩阵的外面： {0，-1}
• 四个方向向量的顺序为顺时针：右下左上，int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
• 初始方向为右
• 循环遍历的时候，先按之前的方向走求出下一个坐标，如果碰壁（坐标跑到矩阵的外面或者遇到之前已经走过的节点）则转弯，换下一个方向（directIndex = (directIndex+1)%4;）这就是碰壁转弯法，如果不碰壁，则还是用之前的方向。
• 确定方向之后求出下一个坐标，然后将这个坐标的值复制到结果数组（或者列表）中
  这里有一个要点，如何判断这个坐标之前已经遍历过了呢，有两种方法
• 直接修改参数二维数组 matrix，将其设置成 -101 即可，因为根据题意 -100 <= matrix[i][j] <= 100
• 如果不让修改 matrix，那就只能创建一个跟 matrix 一样大的 visited 数组了，这个其实跟 图的广度优先遍历bfs 中的 visited 数组的作用是一样的。
  59. 螺旋矩阵 II 中为什么不需要，在那道题中，matrix 只要走过就会有一个非 0 的值，所以用 matrix[x][y] !=0 就可以判断出来 {x,y} 已经被遍历过。
  假设矩阵为 n*m，那么算法的时间复杂度为 O(n*m)

解题

public List<Integer> spiralOrder(int[][] matrix) {
  int rows = matrix.length;
  int cols = matrix[0].length;
  Integer[] resultArr = new Integer[rows * cols];
  int rowNow = 0, colNow = 0;
  int rowMin = 0, rowMax = rows - 1, colMin = 0, colMax = cols - 1;
  for (int i = 0; i < rows * cols; i++) {
    if (colMin == colMax && rowNow <= rowMax) {
      // 不需要考虑转圈
      resultArr[i] = matrix[rowNow][colNow];
      rowNow++;
    } else if (rowMin == rowMax && colNow <= colMax) {
      // 不需要考虑转圈
      resultArr[i] = matrix[rowNow][colNow];
      colNow++;
    } else if (rowNow == rowMin && colNow < colMax) {
      resultArr[i] = matrix[rowNow][colNow];
      colNow++;
    } else if (colNow == colMax && rowNow < rowMax) {
      resultArr[i] = matrix[rowNow][colNow];
      rowNow++;
    } else if (rowNow == rowMax && colMin < colNow) {
      resultArr[i] = matrix[rowNow][colNow];
      colNow--;
    } else if (colNow == colMin && rowMin < rowNow) {
      resultArr[i] = matrix[rowNow][colNow];
      rowNow--;
      if (colNow == colMin && rowNow == rowMin) {
        rowMin++;
        rowMax--;
        colMin++;
        colMax--;
        // 重置起点
        colNow++;
        rowNow++;
      }
    }
  }
  return Arrays.asList(resultArr);
}

上面这种解法是我们在 59. 螺旋矩阵 II 中提出了三种解法中的第一种的延续，
方向向量法

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}};
        int x=0;
        int y=-1;
        int directIndex = 0;
        int m = matrix.length;
        int n = matrix[0].length;
        Integer[] result = new Integer[m*n];
        for(int i=0;i<m*n;i++){
            int newX = x+directions[directIndex][0];
            int newY = y+directions[directIndex][1];
            if(newX<0 || newX > m-1 || newY<0 || newY > n-1  || matrix[newX][newY] == -101){
                directIndex = (directIndex+1)%4;
            }
            x+=directions[directIndex][0];
            y+=directions[directIndex][1];
            // System.out.println(x+":"+y);
            result[i] = matrix[x][y];
            // 通过修改走过的节点来对其进行标记
            // 如果不允许修改matrix 那就得创建一个同等大小的数组来记录 int[] visited = new int[m][n];
            matrix[x][y] = -101;
        }
        return Arrays.asList(result);
    }
}

相关题

59. 螺旋矩阵 II