Python程序 打印螺旋矩阵

本教程的问题陈述是：对于给定的2D矩阵，我们必须设计一种算法，以1D数组的螺旋形式打印它。我们将用Python实现该算法。

了解问题的示例输入和输出：

输入： {{1, 2, 3, 4},
       {5, 6, 7, 8},
       {9, 10, 11, 12},
      {13, 14, 15, 16 }}
输出： 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 
输入： { {1, 3, 5, 7, 9, 11},
      {0, 2, 4, 6, 8, 10},
     {12, 13, 14, 15, 16}}
输出： 1, 3, 5, 7, 9, 11, 10, 16, 15, 14, 13, 12, 0, 2, 4, 6, 8

使用模拟方法解决问题

我们将遵循这个想法，使用模拟方法解决问题：

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

下面是要遵循的步骤：

　* 假设矩阵有m行和n列。
　* Visited[m]表示我们已经访问过的第m行n列的单元格。我们在矩阵中的当前位置表示为（m，n）。它有方向d，并且我们必须遍历m×n个单元格。
　* 随着遍历的继续，指针的下一个位置将由（nr，nc）表示
　* 如果指针在矩阵边界的单元格上并且尚未看到，则它将顺时针旋转90度，然后它将成为指针的下一个位置，即（nr，nc）

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

代码

＃使用模拟方法打印矩阵的螺旋形式的Python程序

＃定义将采用矩阵并返回其螺旋形式的函数
def spiralform（matrix）：
　　螺旋= []

　　＃如果矩阵中没有元素，则返回空数组
　　if（len（matrix）== 0）：
　　　　返回螺旋形式

　　＃存储矩阵的行数m和列数n
　　m = len（matrix）
　　n = len（matrix [0]）

　　＃创建与原始矩阵大小相同的空矩阵
　　visit = [[0 for i in range（n）] for j in range（m）]

　　＃初始化方向向量和坐标
　　dr = [0,1,0，-1]
　　dc = [1,0，-1,0]
　　x = 0
　　y = 0
　　d = 0

　　＃从0到R *C-1迭代
　　for i in range（m * n）：

　　　　＃将当前元素添加到螺旋形式中
       
　　　　螺旋.append（matrix [x] [y]）
　　　　visit [x] [y] = True

　　　　＃将指针移动到下一个位置
　　　　nr = x + dr [d]
　　　　nc = y + dc [d]

　　　　＃检查指针是否在矩阵的边缘，并因此旋转其方向
　　　　如果（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]
　　返回螺旋形式


＃调用函数并将2-D矩阵传递给函数
matrix = [[1,2,3,4]，
    [5,6,7,8]，
    [9,10,11,12]，
    [13,14,15,16]]
print（“结果是：”，end =“”）
＃打印结果数组的元素
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×n）。这是因为我们正在遍历矩阵的每个元素。随着元素的增加，时间复杂度也会增加。

辅助空间：由于查询到的矩阵存储在另一个矩阵中并且我们也使用了矩阵visit，因此此方法需要O（N）额外的内存空间。

将矩阵划分为周期以解决问题

这是我们将遵循的思路：
我们将通过将给定的矩阵分成循环或边界来解决这个问题。我们可以从上面的示例中看到，外层循环项首先以顺时针方式存储，然后存储内层循环项。因此，我们可以使用四个循环来打印所有的循环项。每个循环将用于在特定方向上进行遍历。第一个循环将从矩阵的左侧移动到右侧。然而，第二个循环将从上到下移动，第三个将从右边向左边遍历矩阵，最后一个循环将从底部向上移动。

以下是该方法实现的逐步方法:

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

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

代码

#将矩阵分成循环并打印螺旋形状的Python程序

#定义该函数，该函数将以二维列表形式输入并打印螺旋形式
def spiralform(matrix):
    ''' k - row的开头索引
        m - 最后一行的索引
        l - 列的开头索引
        n - 最后一列的索引 '''
    k = 0
    m = len(matrix)
    l = 0
    n = len(matrix[0])

    # 开始循环，并在k > m或l > n时停止循环。
    while (k < m and l < n):

        # 在剩余的列中，首先从未访问过的行中打印第一行。
        for i in range(l, n):
            print(matrix[k][i], end = " ")

        k = k + 1

        # 打印其余行的最右侧列
        for i in range(k, m):
            print(matrix[i][n - 1], end = " ")

        n = n - 1

        # 打印剩余行的最后一行，用于剩余列
        if (k < m):
            for i in range(n - 1, (l - 1), -1):
                print(matrix[m - 1][i], end = " ")

            m = m - 1

        # 打印剩余列中最左侧的列
        if (l < n):
            for i in range(m - 1, k - 1, -1):
                print(matrix[i][l], end = " ")

            l = l + 1


# 调用该函数并将矩阵传递给它
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)th列，从行k到m打印项目。每次遍历减少n。
• 打印完整的底行。对于k<m的行，即（m-1）th行，请从列n-1到l打印项目。每次遍历减少m。
• 如果l<n，则现在对于左列，请从第（m-1）行到k的索引位置打印第l列的项目。每次遍历增加l。
• 调用该函数，并随矩阵一起传递更新后的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程序，使用DFS递归打印矩阵的螺旋形式

# 定义矩阵的边界
def isInBounds(k, m, l, n):
    if (k < 0 or k >= m or l < 0 or l >= n):
        return False
    return True

# 定义一个函数来检查单元格是否有效
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

# 定义执行DFS算法的函数
def spiralForm(matrix, k, m, l, n, d, spiral):

    # 检查给定索引单元格是否有效
    if (notValid(matrix, k, m, l, n)):
        return

    Blocked = True

    # 向右移动并阻止访问单元格
    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)

    # 将向右移动的单元格添加到结果中
    spiral.append(matrix[k][l])
    matrix[k][l] = -1
    if (Blocked):
        return

    # 此处使用的方向标签：0代表向右，1代表向下，2代表向左，3代表向上
    nxt_k = k
    nxt_l = l
    nxt_d = d

    # 向右移动并相应地更新方向
    if (d == 0):
        if (not notValid(matrix, k, m, l + 1, n)):
            nxt_l += 1
        else:
            nxt_d = 1
            nxt_k += 1

    # 向下移动
    elif(d == 1):
        if (not notValid(matrix, k + 1, m, l, n)):
            nxt_k += 1
        else:
            nxt_d = 2
            nxt_l -= 1

    # 向左移动
    elif(d == 2):
        if (not notValid(matrix, k, m, l - 1, n)):
            nxt_k -= 1
        else:
            nxt_d = 3
            nxt_k -= 1

    # 向上移动
    elif(d == 3):
        if (not notValid(matrix, k - 1, m, l, n)):
            nxt_k -= 1
        else:
            nxt_d = 0
            nxt_l += 1

    # 递归调用该函数并传递更新后的矩阵、方向和结果列表
    spiralForm(matrix, nxt_k, m, nxt_l, n, nxt_d, spiral)

# 遍历矩阵
def spiralTraverse(matrix):
    spiral = []
    spiralForm(matrix, 0, len(matrix), 0, len(matrix[0]), 0, spiral)
    return spiral

# 调用函数并通过以下矩阵传递参数
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)内存空间。可能还有更多解决此问题的方法，但在此处讨论了最基本的方法。