Leetcode-54Spiral-Matrix-螺旋矩阵

50次阅读

共计 1952 个字符,预计需要花费 5 分钟才能阅读完成。

54:Spiral Matrix 螺旋矩阵

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

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

Example 1:

Input:
[[ 1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]
]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input:
[[1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

解题思路:

​ 参考例二,观察索引改变方式:(0,0)—>(0,3)、(0,3)—>((2,3)—>(2,0)—>(1,0)—>(1,2)

​ 从 (0,3) 看,分别是:向下 横坐标自增 1,到 2;向左:纵坐标自减 1,到 0;向上横坐标自减 1,到 1;向右纵坐标自增 1,到 2

​ 假如 m * n 的矩阵,从 (0,m-1) 开始,向下移动 n - 1 次到达最下面,再向左 m - 1 次,向上 n - 2 次,向右 m - 2 次,接着就是:向下 n -3,向左 m -3,向上 n -4,向右 m -4。每次转向 m 或 n 都会自减 1。

这是我的思路,网上很多都是直接操作索引坐标,我觉得不是很好理解,因为超过一个螺旋的矩阵,每次都要更改参考坐标,不过两种方法本质差别不大

java:

class Solution {public List<Integer> spiralOrder(int[][] matrix) {List nums=new ArrayList();
        if (matrix.length==0||matrix[0].length==0)return nums ;
        int row=matrix.length-1,col=matrix[0].length-1,m=0,n=0,i=-1,tmp=0;

        while (row>=0&&col>=0){switch (i++%4){
                case 0:
                    for (tmp=0;tmp<row;tmp++)
                        nums.add(matrix[++m][n]);row-=1;
                    break;
                case 1:
                    for (tmp=0;tmp<col;tmp++)
                        nums.add(matrix[m][--n]);col-=1;
                    break;
                case 2:
                    for (tmp=0;tmp<row;tmp++)
                        nums.add(matrix[--m][n]);row-=1;
                    break;
                case 3:
                    for (tmp=0;tmp<col;tmp++)
                        nums.add(matrix[m][++n]);col-=1;
                    break;
                default:
                    for (tmp=0;tmp<=col;tmp++)
                        nums.add(matrix[m][n++]);tmp=0;n-=1;
                    break;
            }
        }
        return nums;
    }
}

注意点:

​ 先判断是否为空数组,判断条件顺序不能颠倒。因为如果 matrix.length==0 判断为 true,则后面的 matrix[0].length==0 不会再判断,即返回空数组;但是matrix[0].length==0 在前时,如果输入数组为空,matrix[0] 会报错因为 matrix 并没有 0 号索引。

python3:

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if len(matrix)==0 or len(matrix[0])==0:return []
        nums=[];m=0;n=0;row=len(matrix)-1;col=len(matrix[0])-1;flag=0;
        for n in range(col+1):nums.append(matrix[m][n])
        while row>=0 and col>=0:
            if flag % 4 == 0:
                for i in range(row):
                    m+=1
                    nums.append(matrix[m][n])
                row -= 1
            elif flag % 4==1:
                for i in range(col):
                    n-=1
                    nums.append(matrix[m][n])
                col -= 1
            elif flag % 4 == 2:
                for i in range(row):
                    m-=1
                    nums.append(matrix[m][n])
                row -= 1
            elif flag % 4 == 3:
                for i in range(col):
                    n+=1
                    nums.append(matrix[m][n])
                col -= 1
            flag+=1
        return nums

注意点:

​ python 没有 switch…case… 语句。for 循环可操作性很高,可以直接操作索引坐标改变遍历方式,不再赘述。

正文完
 0