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

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 时间复杂度

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 时间复杂度

O(N)

• 这次速度到最快了

4.4 空间复杂度

O(1)

最后

以上就是诚心棒球为你收集整理的算法-面试-顺时针打印矩阵算法-面试-顺时针打印矩阵1 题目概述2 四向依次遍历3 四向依次遍历优化14 四向依次遍历优化2的全部内容，希望文章能够帮你解决算法-面试-顺时针打印矩阵算法-面试-顺时针打印矩阵1 题目概述2 四向依次遍历3 四向依次遍历优化14 四向依次遍历优化2所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。