Spirally Traversing a Matrix in Java

2025年5月6日 | 阅读 5 分钟

螺旋遍历矩阵是指以圆周模式移动通过元素，从左上角开始，沿顶行向右移动。在每次行或列遍历之后，边界都会被调整，并且方向会被切换，持续进行直到所有元素都被探索。此技术提供了以螺旋顺序检索矩阵元素的有效方法。

示例 1

输入

mat[][] = [[1,  2,  3],
           [4,  5,  6],
           [7,  8,  9]]   

输出

 
1 2 3 6 9 8 7 4 5

说明：矩阵从左上角开始按螺旋顺序遍历。

示例 2

输入

mat[][] = [[1,   2,   3,   4],
           [5,   6,   7,   8],
           [9,  10,  11,  12]]   

输出

 
1 2 3 4 8 12 11 10 9 5 6 7

说明：遍历首先沿着外部边界移动，然后到达内部行。

示例 3

输入

mat[][] = [[1,  2],
           [3,  4]]   

输出

 
1 2 4 3

说明：这是一个 2x2 矩阵；螺旋遍历在一个循环中完成。

朴素方法

上述代码中的朴素方法涉及逐层遍历矩阵，从最外层边界开始向内移动。它通过在每次行或列遍历后调整边界，系统地以螺旋顺序打印元素。

算法

步骤 1：设置 top、bottom、left 和 right 来表示矩阵的边缘。

步骤 2：沿着顶边界从左到右遍历并更新 top。

步骤 3：沿着右边界从上到下遍历并更新 right。

步骤 4：沿着底边界从右到左遍历并更新 bottom。

步骤 5：沿着左边界从下到上遍历并更新 left。

实施

文件名：SpiralMatrix.java

import java.util.ArrayList; 
import java.util.List; 
public class SpiralMatrix { 
    // Method to traverse a matrix in spiral order
    public static List<Integer> spirallyTraverse(int[][] matrix) {
        List<Integer> result = new ArrayList<>(); // List to store the elements in spiral order
        int rows = matrix.length; 
        int cols = matrix[0].length; 
        int top = 0; 
        int bottom = rows - 1; // Initialize the bottom boundary of the matrix
        int left = 0; // Initialize the left boundary of the matrix
        int right = cols - 1; // Initialize the right boundary of the matrix
        // Loop to traverse the matrix while there are unvisited rows and columns
        while (top <= bottom && left <= right) {
            // Traverse from left to right along the top row
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]); 
            }
            top++; // Move the top boundary down to the next row
            // Traverse from top to bottom along the right column
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]); 
            }
            right--; // Move the right boundary left to the next column
            // Check if there are still rows to traverse
            if (top <= bottom) {
                // Traverse from right to left along the bottom row
                for (int i = right; i >= left; i--) {
                    result.add(matrix[bottom][i]); 
                }
                bottom--; // Move the bottom boundary up to the previous row
            }
            // Check if there are still columns to traverse
            if (left <= right) {
                // Traverse from bottom to top along the left column
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++; // Move the left boundary right to the next column
            }
        }
        return result; // Return the spiral order result
    }
    // Main method to execute the program
    public static void main(String[] args) {
        // Input matrix to be traversed in spiral order
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        // Call the spirallyTraverse method and store the result
        List<Integer> spiralOrder = spirallyTraverse(matrix);
        // Print the spiral order result
        System.out.println("Spiral order: " + spiralOrder);
    }
}   

输出

 
Spiral order: [1, 2, 3, 6, 9, 8, 7, 4, 5]

时间复杂度：O(N*M)

辅助空间：O(N*M)

空间优化方法

上述代码中的空间优化方法使用常数空间 O(1)，因为它只修改矩阵的边界，而无需任何额外的数据结构。它直接以螺旋顺序打印元素，而无需将它们存储在辅助数组或列表中。

算法

步骤 1：设置 top、bottom、left 和 right。

步骤 2：从左到右打印元素；向上移动 top。

步骤 3：从上到下打印元素；向左移动 right。

步骤 4：如果有效，则从右到左打印元素；向下移动 bottom。

步骤 5：如果有效，则从下到上打印元素；向右移动 left。重复直到边界交叉。

实施

文件名：SpiralMatrixBoundaries.java

public class SpiralMatrixBoundaries { // Class definition
    // Method to traverse the matrix in spiral order
    public static void spirallyTraverse(int[][] matrix) {
        int rows = matrix.length; 
        int cols = matrix[0].length; 
        int top = 0; 
        int bottom = rows - 1; // Initialize the bottom boundary of the matrix
        int left = 0; // Initialize the left boundary of the matrix
        int right = cols - 1; // Initialize the right boundary of the matrix
        // Loop continues until the boundaries cross each other
        while (top <= bottom && left <= right) {
            // Traverse the top row from the left boundary to the right boundary
            for (int i = left; i <= right; i++) {
                System.out.print(matrix[top][i] + " "); 
            }
            top++; // Move the top boundary downward
            // Traverse the right column from the top boundary to the bottom boundary
            for (int i = top; i <= bottom; i++) {
                System.out.print(matrix[i][right] + " ");
            }
            right--; // Move the right boundary leftward
            // Check if there are rows left to traverse (if top boundary hasn't crossed bottom)
            if (top <= bottom) {
                // Traverse the bottom row from the right boundary to the left boundary
                for (int i = right; i >= left; i--) {
                    System.out.print(matrix[bottom][i] + " "); // Print the current element
                }
                bottom--; // Move the bottom boundary upward
            }
            // Check if there are columns left to traverse (if left boundary hasn't crossed right)
            if (left <= right) {
                // Traverse the left column from the bottom boundary to the top boundary
                for (int i = bottom; i >= top; i--) {
                    System.out.print(matrix[i][left] + " ");
                }
                left++; // Move the left boundary rightward
            }
        }
    }
    public static void main(String[] args) { // Main method to execute the program
        // Define a 2D matrix (input)
        int[][] matrix = {
            {1, 2, 3}, // Row 1
            {4, 5, 6}, // Row 2
            {7, 8, 9}  // Row 3
        };
        // Print the message to indicate spiral traversal output
        System.out.println("Spiral order:");
        // Call the spirallyTraverse method to print the matrix in spiral order
        spirallyTraverse(matrix);
    }
}   

输出

 
Spiral order:
1 2 3 6 9 8 7 4 5

时间复杂度：O(N*M)，其中 N 是矩阵的行数，M 是矩阵的列数。程序访问每个元素恰好一次。

辅助空间：O(1)，因为遍历是在原地进行的，不使用任何额外的数据结构。

下一个主题最长公共子序列

Spirally Traversing a Matrix in Java

朴素方法

算法

实施

空间优化方法

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Spirally Traversing a Matrix in Java

朴素方法

算法

实施

空间优化方法

算法

实施

相关帖子

Java 中的 ClosedChannelException 及其示例

Java 中的最大正方形矩阵问题

Java 中的有效正方形问题

Java BiConsumer Interface

Java 中的架构中立是什么

如何在 Java 中将 double 转换为 string

How to Print Table in Java

Java 中将 JSON 转换为 XML

Legacy Class in Java

Java 中的索引映射（或允许负数的平凡哈希）

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器