题解 | #顺时针打印矩阵#

顺时针打印矩阵

http://www.nowcoder.com/practice/9b4c81a02cd34f76be2659fa0d54342a

描述

这是一篇面对初级coder的题解。
知识点：矩阵
难度：二星

题解

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵：

[[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,16]]

则依次打印出数字

[1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]

方法一：转圈打印

思路：记录边界，用循环转圈打印，边界碰撞后结束

class Solution {
public:
    vectorprintMatrix(vector matrix) {
        if (matrix.empty()) return {};
        vectorans;//答案预存
        int left = 0;                      //左边界
        int right = matrix[0].size() - 1;   //右边界
        int up = 0;                      //上边界
        int down = matrix.size() - 1;      //下边界
        while (true)
        {
            //left -> right
            for (int i = left; i <= right; i++) ans.push_back(matrix[up][i]);//上面第一行 if (++up > down) 
                break;//删除第一行 同时上下边界碰撞结束
            //up -> down
            for (int i = up; i <= down; i++) ans.push_back(matrix[i][right]);//右侧最后一列 if (--right < left) break;//删除最后一列 同时左右边界碰撞结束 //right -> left
            for (int i = right; i >= left; i--) //下面最后一行
                ans.push_back(matrix[down][i]);
            if (--down < up) break;//删除最后一行 同时上下边界碰撞结束 //down -> up
            for (int i = down; i >= up; i--) //左侧第一列
                ans.push_back(matrix[i][left]);
            if (++left > right) 
                break;//删除第一列 同时左右边界碰撞结束
        }
        return ans;
    }
};

设矩阵长宽分别为m，n，则时间复杂度和空间复杂度都是O(mn)，因为完整遍历了一遍

运行时间3ms 占用内存492KB

方法二：旋转矩阵

每次打印并删除第一行，旋转矩阵

c++旋转矩阵要自己实现——挺麻烦的

用python来演示

# -*- coding:utf-8 -*-
class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        res = []#初始化返回列表
        while matrix:
            res += matrix.pop(0)#提取第一行
            matrix = list(zip(*matrix))[::-1]#旋转90度
        return res
        # write code here

矩阵旋转

zip(*matrix) 解压
 map(list, _) 将 zip 对象转为 list 
list(_)[::-1] 将 map 对象转为 list 并翻转

python库函数更灵活，但是执行效率低

虽然代码行数少，但是旋转矩阵就是一个O(n)的操作

所以时间和空间复杂度都是O(n^2)

运行时间59ms 占用内存6920KB

方法三：标记矩阵换向

用一个一样大的数组标记是否走过

遇到阻碍换向

class Solution {
public:
    vectorprintMatrix(vector matrix) {
        vectorans;//返回值
        if(matrix.empty()) 
            return ans;// 输入为空直接返回
        int n = matrix.size();//长
        int m = matrix[0].size();//宽
        vector sign(n, vector(m, false));//标记走没走过
        int dx[4] = { 0, 1, 0,-1,}, dy[4] = {1, 0, -1,0};//方向
        int x = 0, y = 0, d = 0;//d控制着方向
        int X,Y;//探点
        for(int i = 0; i < n * m; i++) { ans.push_back(matrix[x][y]);//记录走过的点 sign[x][y] = true;//更新标记 //试探向前走一步 X = x + dx[d]; Y = y + dy[d]; if(X < 0 || X >= n || Y < 0 || Y >= m || sign[X][Y])//遇到阻碍 边界或走过的点
            {
                d = (++d)% 4;//d改变方向
                X = x + dx[d], Y = y + dy[d];//更新遇到阻碍的那个点
            }
            x = X, y = Y;//从更新后的点开始
        }
        return ans;
    }
};

设矩阵长宽分别为m，n，则时间复杂度是O(mn)，因为完整遍历了一遍

但是由于开了一个sign数组记录，空间复杂度变为O(2mn)

运行时间4ms 占用内存520KB