【矩阵】54. 螺旋矩阵【中等】

螺旋矩阵

  • 给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。

示例 1:

在这里插入图片描述

输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]

解题思路

  • 1、模拟顺时针螺旋顺序遍历矩阵的过程。
  • 2、使用四个变量表示当前的上下左右边界,初始化为矩阵的边界。
  • 3、按照顺时针螺旋顺序遍历矩阵,依次沿着上、右、下、左四个方向遍历。
  • 4、每次遍历完成一个方向后,更新对应的边界,并判断是否需要继续遍历。

java实现

public class SpiralMatrix {
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return result;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;

        int top = 0, bottom = rows - 1, left = 0, right = cols - 1;
        //保证旋转区域是合法的且不会越界。
        // 如果这两个条件不满足,说明已经遍历完了所有的行或列
        while (top <= bottom && left <= right) {
            // 遍历上边界
            for (int j = left; j <= right; j++) {
                result.add(matrix[top][j]);
            }
            top++;

            // 遍历右边界
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            right--;

            // 检查是否还有下边界
            if (top <= bottom) {
                // 遍历下边界
                for (int j = right; j >= left; j--) {
                    result.add(matrix[bottom][j]);
                }
                bottom--;
            }

            // 检查是否还有左边界
            if (left <= right) {
                // 遍历左边界
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        int[][] test = {
                { 1,  2,  3,  4},
                { 5,  6,  7,  8},
                { 9, 10, 11, 12},
                {13, 14, 15, 16}
        };
        List<Integer> result = spiralOrder(matrix);
        System.out.println("顺时针螺旋顺序遍历结果: " + result);
        List<Integer> result2 = spiralOrder(test);
        System.out.println("顺时针螺旋顺序遍历结果: " + result2);
    }
}

时间空间复杂度

时间复杂度:O(m * n),其中 m 和 n 分别是矩阵的行数和列数
空间复杂度:O(1),只需要使用常数级别的额外空间

上一篇:WPF意外无法启动?try-catch也无法捕捉?0xc0000409?-原因


下一篇:抖去推无人直播+矩阵托管+AI文案撰写一体化工具如何开发搭建