【题目描述】

AcWing 40. 顺时针打印矩阵

【思路】
模拟 注意边界
空间复杂度：只有一维数组的空间消耗,O(n)
每一个格子只走一遍，时间复杂度为O(n *m)

class Solution {
    public int[] printMatrix(int[][] f) {
        if( f.length == 0 || f[0].length == 0) return new int[]{};//返回空数组

        int m = f.length, n = f[0].length;
        int[] a = new int[m * n];
        int x = 0, y = 0; //起点
        int k =  0; 
        int d = 0;
        while(k < m * n)
        {
            //向右走
            while(k < m * n && y < n - d) a[k ++] = f[x][y++];

            //向下走
            y --; //y出界了要走回来
            x =  x + 1;
            while(k < m * n && x < m - d) a[k ++] = f[x ++][y];

            //向左走
            x --; //x出界了要走回来
            y = y - 1;
            while(k < m * n && y >= 0 + d) a[k ++] = f[x][y --];

            //向上走
            y ++; //y出界了要走回来
            x = x - 1;
            while(k < m * n && x > 0 + d) a[k ++] = f[x --][y];
            ///x出界了要走回来
            x ++;
            y ++;
            d ++;
        }

        return a;
    }
}

解法二： 方向数组 标记判重

用标记数组来作为调换方向的条件，来实现顺时针走位。

空间复杂度：用到了标记数组，空间消耗,O(nm)
每一个格子只走一遍，时间复杂度为O(n m)

class Solution {
    public int[] printMatrix(int[][] f) {
        if( f.length == 0 || f[0].length == 0) return new int[]{};//返回空数组

        int m = f.length, n = f[0].length;
        int[] g = new int[m * n];
        boolean st[][] = new boolean[m][n];
        int dx[] ={0, 1, 0, -1},dy[]={1, 0, -1, 0};
        int d = 0;

        int x = 0, y = 0; //起点
        for(int i = 0; i < m * n; i ++)
        {
            g[i] = f[x][y];
            st[x][y] = true;
            int a = x + dx[d], b = y + dy[d];
            if(a < 0 || a >=m || b < 0 || b >= n || st[a][b]){
                //走重复或者越界了（数组越界/该方向走到头了） 改变方向
                d = (d + 1) % 4;//换一个方向
                a = x + dx[d];
                b = y + dy[d];
            }
            x = a;
            y = b;
        }
        return g;
    }
}