按顺时针打印矩阵

存在二种解题思路: 一种是递归解法,一种是层层递进解法

图解递归解法

如图所示, 一个5*5的矩阵
先打印最外层的圈, 然后剩余最里层3*3的矩阵, 如图.
将3*3的矩阵继续打印最外层,思路与打印最外层思路一样,我们就可以考虑使用递归实现.
最后只剩余一个元素,也可以看成一个矩阵,不过不同大小的矩阵会出现不同形状的矩阵.共3种情况, 如下图.

如图所示, 共三种情况
一个方向的情况
三个方向的情况
四个方向的情况

代码实现思路

矩阵用代码表示为二维数据
首先遍历第一行所有的元素,即图中的从左到右箭头的数据.
然后遍历最右边的元素,即最后一列数据.即图中的从上到下箭头的数据.
再遍历最后一行元素,即图中从右到左箭头的数据
最后遍历最左列的元素,即图中从下到上箭头的数据.
将剩余的矩阵构建成一个子矩阵,即新的二维数组,然后递归传递.这是关键的一步
仅剩余1行1列即是递归退出条件

图解非递归解法

如图所示,我们可以将矩阵看作层层递进的矩阵,如俄罗斯的套娃一样.
第一个套娃的起点坐标,即(0,0)
第二个套娃的起点坐标,即(1,1)
第三个套娃的起点坐标,即(2,2)

代码实现思路

设置一个起点坐标start=0, 然后按方向遍历元素,与递归遍历一样.
我们发现5 5的矩阵, 最后一个圈坐标为(2,2), 4 4矩阵最后一个圈的坐标是(1,1),得出退出条件X坐标大于2倍起点坐标.Y坐标同理可得.
for x > 2 start && y > 2 start, 遍历完第1层圈,再遍历第2层圈, 即start++

代码片段

//解题3思路: 每一次从最左上角打印,即坐标为(0,0),打印最外层一圈. 然后打印第二圈,即坐标:(1,1), 以次类推
//时间复杂度:O(n)
func PrintMatrixLikeSnake(matrix [][]int) []int {
    if len(matrix) <= 0 {
        return nil
    }
    rows := len(matrix)
    columns := len(matrix[0])
    if columns <= 0 {
        return nil
    }
    //定义一个结果集
    result := make([]int, 0)
    //准备打印第一个最外层的圈,定义一个启始坐标
    start := 0
    //我们发现5*5的矩阵, 最后一个圈坐标为(2,2), 4*4矩阵最后一个圈的坐标是(1,1),得出退出条件X坐标大于2倍起点坐标.Y坐标同理可得.
    for rows > start * 2 && columns > start * 2 {
        endX := columns-1-start
        endY := rows-1-start
        //从左到右打印,即第一行的边
        for i := start; i <= endX; i++ {
            result = append(result, matrix[start][i])
        }
        //从最右边从上到下打印,即最右边的边
        if start < endY {
            for i := start+1;i <= endY; i ++ {
                result = append(result, matrix[i][endX])
            }
        }
        //从最右边从右到左打印,即最下面的边
        if start < endX && start < endY {
            for i := endX-1; i >= start; i -- {
                result = append(result, matrix[endY][i])
            }
        }
        //从最左边从下到上打印,即最左边的边
        if start < endY - 1 {
            for i := endY-1; i >= start+1; i -- {
                result = append(result, matrix[i][start])
            }
        }
        start ++
    }
    return result
}