算法-面试-顺时针打印矩阵

素颜马尾好姑娘i 2023-02-15 14:58 23阅读 0赞

# 算法-面试-顺时针打印矩阵 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/

## 1.2 题目描述 ##

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1：

输入：matrix = \[\[1,2,3\],\[4,5,6\],\[7,8,9\]\]  
输出：\[1,2,3,6,9,8,7,4,5\]  
示例 2：

输入：matrix = \[\[1,2,3,4\],\[5,6,7,8\],\[9,10,11,12\]\]  
输出：\[1,2,3,4,8,12,11,10,9,5,6,7\]

限制：

0 <= matrix.length <= 100  
0 <= matrix\[i\].length <= 100

# 2 四向依次遍历 #

## 2.1 思路 ##

要顺时针打印，即右->下->左->上->右。。。直到最后一个元素。

## 2.2 代码 ##

class Solution { 
        public int[] spiralOrder(int[][] matrix) { 
            
            if(matrix == null || matrix.length == 0){ 
                return new int[]{ };
            }
            int m = matrix.length;
            int n = matrix[0].length;
            int[] result = new int[m * n];
            // 先往右，不能再往右就往下，不能往下就往左，不能往左就往上，不能往上就往右
            boolean[] visited = new boolean[m * n];
            // int index = 0;
            // 遍历计数
            int k = 0;
            // 当前方向
            int selected = 0;
            // 右、下、左、上
            int[] direction = { 1, n, -1, -n};
            int i = 0;
            int j = 0;
            int index = i * n + j;
            while(i * n + j < result.length && !visited[i * n + j]){ 
                index = i * n + j;
                visited[index] = true;
                result[k++] =  matrix[i][j];
                index += direction[selected];
                if(selected == 0){ 
                    if(j == n - 1 || visited[index]){ 
                        i++;
                        selected++;
                    } else
                        j++;    
                } else if (selected == 1 ){ 
                    if(i == m - 1 || visited[index]){ 
                        j--;
                        selected++;
                    } else
                        i++;
                    
                } else if (selected == 2 ){ 
                    if(j == 0 || visited[index]){ 
                        i--;
                        selected++;
                    } else
                        j--;
                } else if (selected == 3 ){ 
                    if(i == 0 || visited[index]){ 
                        j++;
                        selected = 0;
                    }  else
                        i--;
                }
            }
            return result;
    
        }
    }

## 2.3 时间复杂度 ##

4ms

O(N)

## 2.4 空间复杂度 ##

O(N)

# 3 四向依次遍历优化1 #

## 3.1 思路 ##

前面方法中虽然时间复杂度为O(N)，但是实际执行时间却很慢，原因是每趟遍历都需要大量判断语句。

其实在每次开始转换方向后的遍历，是可以预测需要在该方向走几步的。

比如4\*3的矩阵：

1.  从矩阵外向(0,0)开始从左往右走，能走4步，
2.  然后向下走2步，
3.  向左走4-1=3步，
4.  向上走2-1=1步，
5.  向右走2步，
6.  顺时针遍历完毕

可以观察到，每次走完一个方向后，下次和该方向平行的方向可走步数为当前可走步数减一。

同时，这样能预测步数的走法，所以就没有必要记录某个元素是否访问过，空间复杂度降为O(1)。

## 3.2 代码 ##

*  可修改原数组nums的代码：

class Solution { 
        public int[] spiralOrder(int[][] matrix) { 
            
            if(matrix == null || matrix.length == 0){ 
                return new int[]{ };
            }
            int m = matrix.length;
            int n = matrix[0].length;
            int[] result = new int[m * n];
            // 先往右，不能再往右就往下，不能往下就往左，不能往左就往上，不能往上就往右
            // 遍历计数
            int k = 0;
            // 当前方向
            int selected = 0;
            int i = 0;
            int j = 0;
            int horizontalMove = n;
            int horizontalMoveRecord = horizontalMove;
            int verticalMove = m - 1;
            int verticalMoveRecord = verticalMove;
            while(k < result.length){ 
                if(selected == 0){ 
                    while(true){ 
                        result[k++] =  matrix[i][j];
                        if(--horizontalMove == 0){ 
                            break;
                        }
                        j++;
                    }
                    // 往右移动完毕，开始转为往下移动
                    i++;
                    selected++;
                    horizontalMove = --horizontalMoveRecord;
                } else if (selected == 1 ){ 
                    while(true){ 
                        result[k++] =  matrix[i][j];
                        if(--verticalMove == 0){ 
                            break;
                        }
                        i++;
                    }
                    j--;
                    selected++;
                    verticalMove = --verticalMoveRecord;
                } else if (selected == 2 ){ 
                    while(true){ 
                        result[k++] =  matrix[i][j];
                        if(--horizontalMove == 0){ 
                            break;
                        }
                        j--;
                    }
                    i--;
                    selected++;
                    horizontalMove = --horizontalMoveRecord;
                } else if (selected == 3 ){ 
                    while(true){ 
                        result[k++] =  matrix[i][j];
                        if(--verticalMove == 0){ 
                            break;
                        }
                        i--;
                    }
                    j++;
                    selected = 0;
                    verticalMove = --verticalMoveRecord;
                }
            }
            return result;
    
        }
    }

## 3.3 时间复杂度 ##

![在这里插入图片描述][20200606101033287.png]  
O(N)

*  这次速度大幅提升。

## 3.4 空间复杂度 ##

O(1)

*  同时，这样能预测步数的走法，所以就没有必要记录某个元素是否访问过，空间复杂度降为O(1)。

# 4 四向依次遍历优化2 #

## 4.1 思路 ##

前面分析过，每次转向后走的步数可预测，所以可以再次优化，省去判断当前方向代码。

## 4.2 代码 ##

class Solution { 
    
        // 遍历计数
        int k = 0;
        // 当前方向
        int selected = 0;
        int i = 0;
        int j = 0;
        
        int horizontalMoveRecord = 0;
        int verticalMoveRecord = 0;
        int moveSteps = 0;
        public int[] spiralOrder(int[][] matrix) { 
            
            if(matrix == null || matrix.length == 0){ 
                return new int[]{ };
            }
            int m = matrix.length;
            int n = matrix[0].length;
            horizontalMoveRecord = n;
            verticalMoveRecord = m - 1;
            moveSteps = horizontalMoveRecord;
            int[] result = new int[m * n];
            // 先往右，不能再往右就往下，不能往下就往左，不能往左就往上，不能往上就往右
            
            horizontalMove(1, 1, result, matrix);
            return result;
        }
        private void horizontalMove(int iIncrement, int jIncrement, int[] result, int[][] matrix){ 
            if(k == result.length){ 
                return;
            }
            while(true){ 
                result[k++] =  matrix[i][j];
                if(--moveSteps == 0){ 
                    break;
                }
                j += jIncrement;;
            }
            // 水平移动完毕，开始转为往下移动
            i += iIncrement;
            horizontalMoveRecord--;
            moveSteps = verticalMoveRecord;
            verticalMove(iIncrement, 0 - jIncrement, result, matrix);
        }
    
        private void verticalMove(int iIncrement, int jIncrement, int[] result, int[][] matrix){ 
            if(k == result.length){ 
                return;
            }
            while(true){ 
                result[k++] =  matrix[i][j];
                if(--moveSteps == 0){ 
                    break;
                }
                i += iIncrement;
            }
            j += jIncrement;
            verticalMoveRecord--;
            moveSteps = horizontalMoveRecord;
            horizontalMove(0 - iIncrement, jIncrement, result, matrix);
        }
    }

## 4.3 时间复杂度 ##

![在这里插入图片描述][20200606104004259.png]  
O(N)

*  这次速度到最快了

## 4.4 空间复杂度 ##

O(1)

[20200606101033287.png]: https://img-blog.csdnimg.cn/20200606101033287.png
[20200606104004259.png]: https://img-blog.csdnimg.cn/20200606104004259.png