Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

螺旋矩阵

Posted on Edited on In , ,
Symbols count in article: 3.5k Reading time ≈ 3 mins.

来源Leetcode第54题螺旋矩阵

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

找规律

从最外层向内部逐层遍历打印矩阵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> ans = new ArrayList<>();
    if(matrix == null || matrix.length == 0)
        return ans;
    int xLength = matrix.length; //定义x方向长度 即行数
    int yLength = matrix[0].length; //定义y方向长度 即列数


    int level = 0; // 初始化层数
    int TotalLevel = (Math.min(xLength,yLength) + 1) / 2;
    //初始化遍历总的层数

    while (level < TotalLevel){
        //对应着最上层向右的第一次遍历
        for(int j = level;j < yLength - level;j++){
            ans.add(matrix[level][j]);
        }
        //对应着第二次遍历从右上往右下
        //这时候的起点注意行数 + 1
        for(int j = level + 1 ; j < xLength - level ; j++)
            ans.add(matrix[j][yLength - 1 - level]);
        //右下往左下如果这一层只有1行，那么第一个循环已经将该行打印了
        // 这里就不需要打印了，即 xLength - 1 - level != level
        for(int j = yLength - level - 2; j >= level && xLength - 1 - level != level;j--)
            ans.add(matrix[xLength - level - 1][j]);
        //从左下往左上,如果这一层只有1列，那么第2个循环已经将该列打印了，
        // 这里不需要打印，即yLength - 1 - level != level
        for(int j = xLength - level - 2 ; j >= level + 1 && yLength - 1 - level != level ;j--)
            ans.add(matrix[j][level]);
        level ++ ;
    }
    return ans;
}

模拟

来源题解

绘制螺旋轨迹路径，我们发现当路径超出界限或者进入之前访问过的单元格时，会顺时针旋转方向。
假设数组有 R 行 C 列，seen[r][c] 表示第 r 行第 c 列的单元格之前已经被访问过了。当前所在位置为 (r, c)，前进方向是 di。我们希望访问所有 R x C 个单元格。
当我们遍历整个矩阵，下一步候选移动位置是 (cr, cc)。如果这个候选位置在矩阵范围内并且没有被访问过，那么它将会变成下一步移动的位置；否则，我们将前进方向顺时针旋转之后再计算下一步的移动位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
  public List<Integer> spiralOrder(int[][] matrix) {
      List ans = new ArrayList();
      if (matrix.length == 0) return ans;
      int R = matrix.length, C = matrix[0].length;
      boolean[][] seen = new boolean[R][C];
//定义了4个方向数组，分别对应y+1 x+1 x-1 y-1
      int[] dr = {0, 1, 0, -1};
      int[] dc = {1, 0, -1, 0};
      int r = 0, c = 0, di = 0;
      for (int i = 0; i < R * C; i++) {
          ans.add(matrix[r][c]);
          seen[r][c] = true;
          int cr = r + dr[di];
          int cc = c + dc[di];
          if (0 <= cr && cr < R && 0 <= cc && cc < C && !seen[cr][cc]){
              r = cr;
              c = cc;
          } else {
	//越界之后换向
              di = (di + 1) % 4;
              r += dr[di];
              c += dc[di];
          }
      }
      return ans;
  }
优化模拟

对题解的代码做了一定的优化，减少了空间使用度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> ans = new ArrayList<>();
    if(matrix == null || matrix.length == 0)
        return ans;
    //4次转向的方向
    int [] dir_i = {0,1,0,-1};
    int [] dir_j = {1,0,-1,0};
    //定义行数和列数
    int row = matrix.length;
    int cols = matrix[0].length;
    int count = 0;
    int index = 0; // 方向索引
    int countsAll = row * cols;
    int pos_i = 0, pos_j = -1 ; //位置索引
    int len;
    while (count < countsAll){
        //获得当前遍历行或列的长度
        if(index == 0 || index == 2)
            len = cols;
        else len = row;

        for(int i = 0 ; i < len ; i++){
            //遍历行or列

            //计算当前位置
            pos_i = pos_i + dir_i[index];
            pos_j = pos_j + dir_j[index];
            ans.add(matrix[pos_i][pos_j]);
            count ++ ;
            if(count == countsAll)
                return ans;
        }

        if(index == 0 || index == 2)
        //更新边界值
            row--;
        else if (index == 1 || index == 3)
            cols--;

        index = (index + 1) % 4; // 换向
    }
    return  ans;
}

层遍历

对于每层，我们从左上方开始以顺时针的顺序遍历所有元素，假设当前层左上角坐标是 (r1, c1)，右下角坐标是 (r2, c2)。

首先，遍历上方的所有元素 (r1, c)，按照 c = c1,…,c2 的顺序。然后遍历右侧的所有元素 (r, c2)，按照r = r1+1,…,r2 的顺序。如果这一层有四条边（也就是 r1 < r2 并且 c1 < c2 ），我们以下图所示的方式遍历下方的元素和左侧的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List < Integer > spiralOrder(int[][] matrix) {
    List ans = new ArrayList();
    if (matrix.length == 0)
        return ans;
    int r1 = 0, r2 = matrix.length - 1;
    int c1 = 0, c2 = matrix[0].length - 1;
    while (r1 <= r2 && c1 <= c2) {
        for (int c = c1; c <= c2; c++) ans.add(matrix[r1][c]);
        for (int r = r1 + 1; r <= r2; r++) ans.add(matrix[r][c2]);
        if (r1 < r2 && c1 < c2) {
            for (int c = c2 - 1; c > c1; c--) ans.add(matrix[r2][c]);
            for (int r = r2; r > r1; r--) ans.add(matrix[r][c1]);
        }
        r1++;
        r2--;
        c1++;
        c2--;
    }
    return ans;
}