Skip to content

Latest commit

 

History

History
57 lines (46 loc) · 1.89 KB

README.md

File metadata and controls

57 lines (46 loc) · 1.89 KB

054.螺旋矩阵

问题描述

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

示例 1:

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

示例 2:

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

问题分析

  这个题目其实是一个对矩阵下标进行操作的题目,很容易想到按层来对矩阵进行操作,每次对最外层进行遍历。可以发现按层遍历的起点是在于每一层的起点都是(i,i),如示例2中,第一层的起点是1,坐标为(0,0);第二层的起点是6,坐标为(1,1)······所以确定每次外循环的起点为(i,i),然后从起点分别依次进行向右、向下、向左、向上的遍历。
  这里为了规避动态考虑边界条件,即不用根据起点的不同来动态计算边界坐标,我增设了一个flag标记二维数组,已经遍历过的点我会将该坐标的flag数组置1,所以在各个方向的遍历中,如果flag值0则继续遍历,否则可以认为已经碰到当前层的边界,直接进行下一个方向的遍历即可。这样考虑是因为可以发现每次改变方向都是已经碰到上一层的数据点,故可以用flag数组的空间来换取考虑每个方向的边界条件的繁琐。

部分代码

  这里只列出向右和向上的遍历,其他两个方向类似,具体代码见附件。

    //向右
    int fx=i,fy=i;
    while ((fy<col)&&(flag[fx][fy]==0)){  
        list.add(matrix[fx][fy]);
        flag[fx][fy]=1;     //标记已经取过的地址
        fy++;
    }
    //向上
    fx--;fy++;
    while ((fx>=0)&&(flag[fx][fy])==0){
        list.add(matrix[fx][fy]);
        flag[fx][fy]=1;
        fx--;
    }