在顺时针螺旋中查找in的螺旋2D矩阵(列表列表)

Question

在接受微软的采访时，我得到了这个问题。

这个问题叫做2D蛇。我想知道我的解决方案1是否通过了测试，但我的解决方案1是否与解决方案2不同。

让我们一起玩2D矩阵吧！编写一个方法find_spiral，以顺时针螺旋顺序遍历in的2D矩阵(列表列表)，并将元素附加到整数的输出列表中。示例:输入矩阵:输出列表：

解决方案1

def find_spiral(matrix):

    output = []

    while matrix:
        row = matrix.pop(0)
        output.extend(row)
        matrix = zip(*matrix)[::-1] 

    return output

解决方案2

def find_spiral(matrix):    
    spiral_list = []
    if matrix == None or len(matrix) == 0:
        return list
    m = len(matrix) 
    n = len(matrix[0])
    x=0
    y=0

    while(m>0 and n>0):
        if(m==1):
            i = 0
            while i < n:
                spiral_list.append(matrix[x][y])
                i += 1
                y += 1
            break
        elif(n==1):
            i = 0
            while i < m:
                spiral_list.append(matrix[x][y])
                i += 1
                x += 1
            break

        i = 0
        while i < n-1:
            spiral_list.append(matrix[x][y])
            i+=1
            y+=1

        j = 0
        while j < m-1:
            spiral_list.append(matrix[x][y])
            j+=1
            x+=1

        i = 0
        while i < n-1:
            spiral_list.append(matrix[x][y])
            i+=1
            y-=1

        j = 0
        while j < m-1:
            spiral_list.append(matrix[x][y])
            j+=1
            x-=1

        x+=1
        y+=1
        m=m-2
        n=n-2

    return spiral_list

测试用例：

Input   
[[1,2],[3,4]]
Expected Result
[1, 2, 4, 3]
Input
[[1,2],[3,4]
Expected Result
[1, 2, 4, 3]

Input
[[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Expected Result
[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

input
[[1,2],[3,4]
Expected Result
[1, 2, 3, 4, 5, 6, 12, 18, 17, 16, 15, 14, 13, 7, 8, 9, 10, 11]

Input
[[1,0],[0,1]]
Expected Result
[1, 0, 1, 0]

Input
[[1,2,3],[4,5,6],[7,8,9]]
Expected Result
[1, 2, 3, 6, 9, 8, 7, 4, 5]

Answer 1

只是回顾解决方案1。

1. 这个解决方案很聪明(反复提取第一行，将剩余部分旋转四分之一圈)，代码简洁。
2. 但是，代码通过弹出第一行来破坏性地修改输入matrix。这对调用者来说是令人惊讶的，并且可能会使其更难使用或测试。
3. 该代码在Python3中不起作用:它失败了，只有例外: TypeError：'zip‘对象在Python3中是不可订阅的，您必须编写list(zip(...))。由于Python2.7是接近生命的尽头，所以编写易于移植到Python3的代码是个好主意。在本例中，您可以从future_builtins导入zip中获得与Python3兼容的内置zip函数的版本。
4. 如果输入是n×n\$矩阵，则剩余的旋转需要O(n^2)\$，这必须执行\O(N)\$次，从而导致总的运行时为O(n^3)\$。但从直觉上看，应该可以在O(n^2)内输出螺旋线。我们可以通过实现同样的方法(重复提取第一行并以四分之一圈旋转剩余部分)来实现这一点，但是我们没有修改矩阵，而是修改了我们的坐标系。如果我先给出代码: def find_spiral_2(矩阵)：“按顺时针螺旋顺序返回矩阵元素的列表”，这可能是最简单的。h，w=len(矩阵)，len(矩阵)#余数i的高度和宽度，j= 0，-1 #在螺旋di中的电流位置，dj = 0，1#当前运动方向螺旋= []而h> 0：#输出顶部行为_ in范围(W)：i += di j += dj spiral.append(矩阵)#移除顶行并旋转四分之一转h，w= w，h-1 di，dj = dj，-di返回螺旋线的工作方式是，我们将算法的状态保持为矩阵其余部分的高度h和宽度w\n，我们沿着螺旋的当前位置的坐标\(i，j)\\，以及一个向量\(di，dj)\给出沿着螺旋路径的当前运动方向。要输出上一行，我们按照\$w\$步骤的当前方向，将我们保留在矩阵的右上角(其余部分)。然后，就像在您的解决方案中一样，我们移除顶部的行，并通过四分之一转弯旋转剩下的部分，或者更确切地说，我们修改我们的坐标以达到这个效果。从\$h\$中删除顶部行减去1。将剩余部分通过四分之一圈旋转会导致\w\n和h\\h交换(高度变为宽度，反之亦然)，而当前的移动方向则通过四分之一圈旋转。您应该检查行di, dj = dj, -di是否实现了这一点。应该清楚的是，这不会修改matrix，并根据需要在\$O(n^2)\$中运行。