Python 程序打印螺旋矩阵

2024年8月29日 | 13分钟阅读

本教程的问题陈述是：给定一个二维矩阵，我们需要设计一个算法来以一维数组的螺旋形式打印它。我们将在 Python 中实现该算法。

样本输入和输出以理解问题

Input: {{1, 2, 3, 4},
       {5, 6, 7, 8},
       {9, 10, 11, 12},
      {13, 14, 15, 16 }}
Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 
Input: { {1, 3, 5, 7, 9, 11},
      {0, 2, 4, 6, 8, 10},
     {12, 13, 14, 15, 16}}
Output: 1, 3, 5, 7, 9, 11, 10, 16, 15, 14, 13, 12, 0, 2, 4, 6, 8

使用模拟方法解决问题

我们将遵循此思路，使用模拟方法解决问题

我们将为给定的矩阵或二维数组绘制螺旋路径。螺旋路径必须沿顺时针方向移动。它只会在边缘改变路径或转弯，这样循环就不会超出矩阵的边界。

以下是必须遵循的步骤

设矩阵有 m 行和 n 列。
Visited[m] 将表示 m 行 n 列的单元格，我们已经访问过。我们在矩阵中的当前位置由 (m, n) 表示。它将具有方向 d，并且我们必须遍历总共 m x n 个单元格。
当我们继续遍历时，指针的下一个位置将由 (nr, nc) 表示
如果指针位于矩阵边界且尚未看到的单元格上，则它将顺时针转动 90 度，并成为指针的下一个位置，即 (nr, nc)

现在我们将在 Python 中实现此方法。

代码

# Python program to print the spiral form of the matrix using the simulation approach
  
# Defining the function that will take a matrix and will return its spiral form
def spiralform(matrix):
    spiral = []

    # If there are no elements in the matrix, it will return an empty array
    if (len(matrix) == 0):
        return spiral

    # Storing the number of rows m and the number of columns n of the matrix
    m = len(matrix)
    n = len(matrix[0])

    # Creating an empty matrix of the same size
    visit = [[0 for i in range(n)] for j in range(m)]

    # Intializing the direction vectors and coordinated
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]
    x = 0
    y = 0
    d = 0
  
    # Iterating from 0 to R * C - 1
    for i in range(m * n):

        # Adding the current element to the spiral form
       
spiral.append(matrix[x][y])
        visit[x][y] = True

        # Moving the pointer to the next position
        nr = x + dr[d]
        nc = y + dc[d]

        # Checking if the pointer is at the edge of the matrix and hence rotating its direction
        if (0 <= nr and nr < m and 0 <= nc and nc < n and not(visit[nr][nc])):
            x = nr
            y = nc
        else:
            d = (d + 1) % 4
            x += dr[d]
            y += dc[d]
    return spiral
  
  
# Calling the function and passing a 2-D matrix to the function
matrix = [[1, 2, 3, 4],
      [5, 6, 7, 8],
      [9, 10, 11, 12],
      [13, 14, 15, 16]]

# Printing the elements of the resultant array
for x in spiralform(matrix):
    print(x, end = " ")

输出

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

时间复杂度： 此方法的时间复杂度为 O(m x n)。这是因为我们遍历了矩阵的每个元素。随着元素数量的增加，时间复杂度也会增加。

辅助空间：由于结果矩阵存储在另一个矩阵中，并且我们还使用了矩阵访问，因此此方法需要 O(N) 的额外内存空间。

通过将矩阵划分为周期来解决问题

这是我们将遵循的解决问题的思路

我们将通过将给定的矩阵划分为循环或边界来解决此问题。从上面的例子可以看出，外层循环的元素首先按顺时针存储，然后存储内层循环的元素。因此，我们可以使用四个 for 循环打印所有循环的元素。每个 for 循环将用于沿特定方向遍历。第一个循环将从矩阵的左侧移动到右侧。但是，第二个循环将从上到下移动，第三个循环将从右到左遍历矩阵，最后一个循环将从下到上移动。

以下是实现此方法的详细步骤

我们将首先创建和初始化变量。变量 k 将表示行的起始索引，m 将表示行的结束索引，l 将表示列的起始索引，n 将表示列的结束索引。
我们将运行循环直到每个正方形都被打印出来。
在每一次外层循环遍历中，按顺时针打印正方形的元素。
首先完全打印顶行。但对于后续由 k 表示的行，仅打印第 k 行中从索引 l 到 n 的列的元素。每次遍历增加 k 的计数。
从上到下完全打印右侧或最后一列。对于后续的从上到下遍历，即对于 (n - 1) 列，打印从行 k 到 m 的元素。每次遍历将 n 减 1。
完全打印底行。对于行 k < m，即 (m - 1) 行，打印从列 n - 1 到 l 的元素。每次遍历将 m 减 1。
现在对于左列，如果 l 小于 n，则打印从行索引 (m - 1) 到 k 的 l 列的元素。每次遍历将 l 加 1。

现在我们将在 Python 中实现此方法

代码

# Python program to print the spiral form of the matrix by dividing the matrix into cycles
  
# Defining the function which will take the 2-D list as input and print the spiral form
def spiralform(matrix):
    ''' k - beginning of the row
        m - last row index
        l - beginning of the column
        n - last column index '''
    k = 0
    m = len(matrix)
    l = 0
    n = len(matrix[0])

    # Starting the loop with the condition to stoop the loop when k > m and l > n
    while (k < m and l < n):
  
        # Printing the first row out of the unvisited rows from the remaining columns
        for i in range(l, n):
            print(matrix[k][i], end = " ")
  
        k = k + 1
  
        # Printing the rightmost column out of the remaining columns for the remaining rows
        for i in range(k, m):
            print(matrix[i][n - 1], end = " ")
  
        n = n - 1
  
        # Printing the last row from the remaining rows for the remaining columns
        if (k < m):
            for i in range(n - 1, (l - 1), -1):
                print(matrix[m - 1][i], end = " ")
  
            m = m - 1
  
        # Printing the leftmost column out of the remaining columns
        if (l < n):
            for i in range(m - 1, k - 1, -1):
                print(matrix[i][l], end = " ")
  
            l = l + 1
  

# Calling the function and passing the matrix to it
matrix = [[1, 2, 3, 4],
          [5, 6, 7, 8],
          [9, 10, 11, 12],
          [13, 14, 15, 16]]

spiralform(matrix)

输出

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

时间复杂度：此方法的时间复杂度为 O(m x n)。这是因为我们遍历了矩阵的每个元素。

辅助空间：此方法需要 O(1) 的额外内存空间。我们只创建了额外的整数变量。

使用递归解决问题

这是我们将遵循的解决问题的思路

我们将通过使用递归函数打印矩阵的边界来解决此问题。在每一次递归调用中，我们将减小矩阵的维度。我们将遵循与上一个解决方案相同的逻辑。

以下是实现此方法的详细步骤

我们将创建一个递归函数，该函数将接受矩阵和以下变量
创建一个递归函数，该函数将矩阵和一些变量（k - 行的起始，m - 行的最后索引，l - 列的起始，n - 列的最后索引）作为参数。
检查基本条件，行的起始索引和列的起始索引应在每次递归时小于行和列的结束索引。函数在每次递归时都会按顺时针方式打印矩阵边界上的元素。
首先完全打印顶行。但对于后续由 k 表示的行，仅打印第 k 行中从索引 l 到 n 的列的元素。每次遍历增加 k 的计数。
从上到下完全打印右侧或最后一列。对于后续的从上到下遍历，即对于 (n - 1) 列，打印从行 k 到 m 的元素。每次遍历将 n 减 1。
完全打印底行。对于行 k < m，即 (m - 1) 行，打印从列 n - 1 到 l 的元素。每次遍历将 m 减 1。
现在对于左列，如果 l 小于 n，则打印从行索引 (m - 1) 到 k 的 l 列的元素。每次遍历将 l 加 1。
调用该函数，并将更新后的 k、m、l、n 值与矩阵一起传递给函数。

现在我们将在 Python 中实现此方法

代码

# Python3 program to print the spiral form of the matrix using recursion
  
# Defining the function which will take a 2-D list and other mentioned variables as input and print the spiral form
def spiralForm(matrix, k, m, l, n):

    ''' k - beginning of the row
        m - last row index
        l - beginning of the column
        n - last column index '''

    # If the lower indices pass the maximum value, the function will stop
    if (k >= m or l >= n):
        return
  
    # Printing the first row of the remaining rows
    for i in range(l, n):
        print(matrix[i][i], end = " ")
  
    # Printing the lst column of the remaining columns
    for i in range(k + 1, m):
        print(matrix[i][n - 1], end = " ")
  
    # Printing the last row only if the remaining first and the last rows are not the same
    if ((m - 1) != k):
        for i in range(n - 2, l - 1, -1):
            print(matrix[m - 1][p], end=" ")
  
    # Printing the first remaining column if the remaining last and first column are not the same
    if ((n - 1) != l):
        for i in range(m - 2, k, -1):
            print(matrix[i][l], end = " ")
  
    spiralForm(matrix, k + 1, l + 1, m - 1, n - 1)
  
# Calling the function and passing the matrix to it

matrix = [[1, 2, 3, 4],
          [5, 6, 7, 8],
          [9, 10, 11, 12],
          [13, 14, 15, 16]]
k = 0
m = len(matrix)
l = 0
n = len(matrix[0])
  
# Function Call
spiralForm(matrix, k, m, l, n)

输出

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

时间复杂度：此方法的时间复杂度为 O(m x n)。这是因为我们遍历了矩阵的每个元素。

辅助空间：此方法需要 O(1) 的额外内存空间。我们只创建了额外的整数变量。

使用 DFS 解决问题

这是我们将遵循的解决问题的思路

解决此问题的另一种递归方法是通过考虑给定方形矩阵内的 DFS 移动。DFS 移动是：向右，然后向下，然后向左，然后向上，然后再次向右，并继续此移动，直到我们到达矩阵的最后一个元素（最中间的元素）。

我们将原地修改矩阵，以便当 DFS 算法指针访问每个矩阵单元格时，算法会将其值更改为矩阵无法包含的值。当 DFS 算法到达一个单元格，其所有周围单元格都具有禁止访问的值，或者换句话说，已经访问过时，它将结束迭代。我们将创建一个变量来控制指针的方向。

以下是实现此方法的详细步骤

我们将从创建一个 DFS 函数开始，该函数将接受一个矩阵、单元格的索引以及方向初始化器。
算法将首先检查给定索引的单元格是否有效。有效单元格是指指针之前未访问过的单元格。如果单元格无效，指针将跳过此单元格并转到下一个单元格。
如果单元格有效，我们将打印其值。
由于指针已访问此单元格，我们将通过将其值更改为矩阵不支持的值来标记它。
然后我们需要检查周围的单元格是否有效，或者前一个单元格是否是最后一个。如果是，则停止算法。如果不是，算法将沿指定的参数方向继续。假设方向是向右；指针将向右移动并检查单元格是否有效。如果无效，算法将改变方向，如上所述。它将指向下方。
如果该方向的单元格有效，则打印这些单元格并将其标记为已访问。如果单元格无效或指针已到达矩阵边界，指针将改变方向向左。
然后重复相同的步骤。检查单元格是否有效。如果是，则打印它们并将其标记为已访问。如果无效，或指针已到达单元格边界，则将方向更改为向上。
算法将在向上方向重复相同的步骤。打印有效单元格并将其标记为已访问。如果单元格无效，指针将再次改变方向向右。
一旦指针到达一个单元格，并且所有周围的单元格都已访问，并且没有更多单元格可打印，这个过程将迭代进行。

我们将在 Python 中实现此方法

代码

# Python program to print the spiral form of the matrix using DFS recursion

# Defining the bounds of the matrix
def isInBounds(k, m, l, n):
    if (k < 0 or k >= m or l < 0 or l >= n):
        return False
    return True
  
# Defining a function to check if the cell is valid or not
def notValid(matrix, k, m, l, n):

    spiral = []

    if (not isInBounds(k, m, l, n)):
        return True
    if (matrix[k][l] == -1):
        return True
  
    return False
  
# Defining the function to execute the DFS algorithm
def spiralForm(matrix, k, m, l, n, d, spiral):

    # Check if the given indices' cell is valid or not
    if (notValid(matrix, k, m, l, n)):
        return

    Blocked = True

    # Traversing in the right direction and blocking the visited cells
    for i in range(-1, 2, 2):
        Blocked = Blocked and notValid(matrix, i + k, m, l, n) and notValid(matrix, k, m, i + l, n)

    # Adding cells in the right direction to the result
    spiral.append(matrix[k][l])
    matrix[k][l] = -1
    if (Blocked):
        return
  
    # direction labels used here: 0 is for right, 1 is for down, 2 is for left, 3 is for up
    nxt_k = k
    nxt_l = l
    nxt_d = d

    # Traversing in the right direction and updating the direction accordingly
    if (d == 0):
        if (not notValid(matrix, k, m, l + 1, n)):
            nxt_l += 1
        else:
            nxt_d = 1
            nxt_k += 1

    # Traversing in a downwards direction
    elif(d == 1):
        if (not notValid(matrix, k + 1, m, l, n)):
            nxt_k += 1
        else:
            nxt_d = 2
            nxt_l -= 1

    # Traversing in the left direction
    elif(d == 2):
        if (not notValid(matrix, k, m, l - 1, n)):
            nxt_k -= 1
        else:
            nxt_d = 3
            nxt_k -= 1
    
    # Traversing in the upward direction
    elif(d == 3):
        if (not notValid(matrix, k - 1, m, l, n)):
            nxt_k -= 1
        else:
            nxt_d = 0
            nxt_l += 1

    # Calling the function recursively and passing the updated matrix, directions, and resultant list
    spiralForm(matrix, nxt_k, m, nxt_l, n, nxt_d, spiral)
 
# Traversing the matrix 
def spiralTraverse(matrix):
    spiral = []
    spiralForm(matrix, 0, len(matrix), 0, len(matrix[0]), 0, spiral)
    return spiral
 
# Calling the function and passing the following matrix
matrix = [[1, 2, 3, 4], 
          [5, 6, 7, 8], 
          [9, 10, 11, 12], 
          [13, 14, 15, 16]]

result = spiralTraverse(matrix)
print(result)

输出

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

时间复杂度：此算法的时间复杂度也为 O(m x n)。这是因为我们单独遍历了矩阵的每个元素。

辅助空间：此算法将占用 O(1) 的内存空间。除了递归使用的堆栈之外，此算法不使用任何额外的内存空间。

我们已经看到了打印矩阵螺旋形式的各种方法。所有方法都具有相同的 O(m x n) 时间复杂度，并占用相同的 O(1) 内存空间。可能还有其他方法可以解决此问题，但这里讨论的是最基本的方法。

下一主题使用 Qt Designer 的 Python：更快的 GUI 应用程序开发

Python 程序打印螺旋矩阵

样本输入和输出以理解问题

使用模拟方法解决问题

通过将矩阵划分为周期来解决问题

使用递归解决问题

使用 DFS 解决问题

联系信息

关注我们

教程

面试题

在线编译器

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

Python 问题

Python 程序打印螺旋矩阵

样本输入和输出以理解问题

使用模拟方法解决问题

通过将矩阵划分为周期来解决问题

使用递归解决问题

使用 DFS 解决问题

相关帖子

Python 中的通配符

如何在 Python 中验证电子邮件

使用 Python 解决物理计算问题

计算括号反转次数

Python 中的 Lee 算法

Python IMDbPY - 用于电影的库

如何将列表转换为集合

Python Fiona 模块

使用 Dash 进行 Python 数据可视化界面开发

如何在 Python 中在同一行打印

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器